프로그래머스 - 불량 사용자 / C++

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/64064

코딩테스트 연습 - 불량 사용자

 

문제 풀이

어려워서 검색을 정말 많이 해봤는데 C++ 사용자들은 거의 90% DFS를 통해 풀이하였다. 코딩 테스트 스터디를 진행하며 파이썬 유저들이 순열을 통해 풀이하는 것을 보고 순열을 이용한 풀이가 더 간단하다고 생각해서 순열과 Set을 이용하여 풀었다.

 

아이디어는 다음의 순서와 같다.

1. user_id의 목록을 순열을 통해 모든 경우의 수를 생성한다. 이 때, next_permutation을 사용할 것이기 때문에 정렬이 필요하다.

 

2. 1번의 과정에서 user_id 전체에 대해 순열을 생성하면 안된다. 비교해야할 banned_id의 size와 일치해야 하기 때문에 nPr(n은 user_id의 size, r은 banned_id의 size)의 순열을 생성해야한다. 이를 위해 n size의 vector를 생성하고 r size만큼 원소에 +1을 해준다. 1번 테스트 케이스의 경우에는 5P2이므로 (1, 1, 0, 0, 0)의 벡터가 생성되었을 것이다.

 

3. 생성된 순열을 순회하며 user_id와 banned_id의 패턴이 일치하는지 확인한다. 이를 위해 아래와 같은 함수를 구현한다.

bool checkStr(string a, string b){
    if(a.size() != b.size()) return false;
    
    for(int i=0; i<a.size(); i++){
        if(b[i] == '*') continue;
        if(a[i] != b[i]) return false;
    }
    
    return true;
}

 

4. 패턴이 일치하면 임시 string 벡터에 넣어주고 user_id를 모두 확인하였으면 중복 제거를 위해 정렬 및 set에 추가한다. 이 때, 임시 배열의 사이즈가 banned_id의 size와 일치하는지 확인해야 한다. 앞서 패턴을 확인할 때 일치하기만 하면 임시 배열에 추가하였기 때문에 일치하는 단 하나의 문자열이 있으면 벡터에 들어가있는 상황이기 때문이다.

 

5. 모든 과정이 끝나고나면 set에는 제재 목록의 경우의 수가 들어가있을 것이다. 따라서, set의 size를 리턴해주면 된다.

 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

bool checkStr(string a, string b){
    if(a.size() != b.size()) return false;
    
    for(int i=0; i<a.size(); i++){
        if(b[i] == '*') continue;
        if(a[i] != b[i]) return false;
    }
    
    return true;
}


int solution(vector<string> user_id, vector<string> banned_id) {
    set<vector<string> > s;
    sort(user_id.begin(), user_id.end());//permutation을 위해 정렬
    
    vector<int> v;
    for(int i=0; i<user_id.size(); i++){
        v.push_back(0);
    }
    for(int i=0; i<banned_id.size(); i++){
        v[i] += 1;
    } // n P r
    
    do {
        vector<string> tmp;
        for(int i=0; i<user_id.size(); i++){
            if(v[i] == 1){
                if(checkStr(user_id[i], banned_id[i])){
                    tmp.push_back(user_id[i]);
                }
            }
        }
        
        sort(tmp.begin(), tmp.end());
        
        if(tmp.size() == banned_id.size()){
            s.insert(tmp);
        }
        
    } while(next_permutation(user_id.begin(), user_id.end()));
    //생성된 순열을 순회하며 user_id, banned_id를 확인한다. 일치하면 tmp 배열에 추가한다.
	//정렬과 set을 통해 중복을 제거하고 길이가 조건에 맞으면 insert
    
    return s.size();
}