[프로그래머스] 불량 사용자 (level3, c++)

 

문제

---

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

 

문제조건

---

• user_id 배열의 크기는 1 이상 8 이하입니다.
• user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 응모한 사용자 아이디들은 서로 중복되지 않습니다.
  • 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
• banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
• banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
  • 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
  • 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

 

풀이

---

처음에 문제를 잘못 이해해서 꽤나 해맨 문제였다. 문제를 읽어보면 알 수 있지만 불량 사용자 목록을 만족하는 모든 아이디를 구하는 것이 아니라 불량 사용자 쌍을 구하는 것이다.

가능한 모든 쌍을 구해보면 됨으로 DFS를 사용하여 풀면 된다. 재귀를 사용하였고, 한 쌍에서 이미 포함된 값을 중복하여 포함하지 않기 위해 visited로 확인해 주었다. 중복되는 쌍은 제거해 주어야 함으로 만족하는 쌍을 하나의 문자열로 만들어준 후, set에 넣어 중복을 제거해 주었다.

 

코드

---

#include <string>
#include <vector>
#include <set>
#include <iostream>

using namespace std;
set<string> ans;
bool visited[8];
vector<string> user;
vector<string> ban;

void find(int idx){
    if(idx==ban.size()){
        string s = "";
        for(int i=0; i<8; i++){
            if(visited[i]) {s += user[i];}
        }
        ans.insert(s);
        return;    
    }

    for(int i=0; i<user.size(); i++){
        //이미 결과에 포함
        if(visited[i]) {continue;}

        else{
            bool check = true;

            //길이가 다르면 불가능
            if(user[i].size()!=ban[idx].size()) {continue;}

            //같다면 비교
            else{
                for(int j=0; j<ban[idx].length(); j++){
                    if(ban[idx][j]=='*') continue;
                    else if(ban[idx][j]!=user[i][j]) {
                        check=false;
                    }
                }

                //답이라면 추가
                if(check){
                    visited[i]=true;
                    find(idx+1);
                    visited[i]=false;
                }

            }
        }
    }


}
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    user = user_id;
    ban = banned_id;

    //banned_id의 0번째 index부터 확인
    find(0);

    answer = ans.size();
    return answer;
}