2019 카카오 개발자 겨울 인턴십 불량 사용자 ( C++ )

https://programmers.co.kr/learn/courses/30/lessons/64064

프로그래머스

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

 

 

 

당첨에서 제외되어야 할 제재 아이디 목록이 몇 가지 경우의 수가 가능한 지를 구해야하는데 id배열의 크기가 8 이하이므로 모든 경우를 구해봐도 된다.

 

 

 

먼저 각 불량 아이디에 대해 모든 응모 아이디와 비교하여, 매핑될 수 있는 응모 아이디를 찾아 각각의 응모 아이디에 매핑되는 경우를 조합해준다. 불량 아이디와 매핑 될 수 있는 응모 아이디는 불량 아이디의 *부분을 제외한 모든 문자가 일치해야 하고 문자열의 길이도 같아야 한다.

 

응모 아이디를 제재목록으로 만들어주는 방법은 응모 아이디의 인덱스를 문자열로 만든 후에 이전 제재 목록 문자열과 합쳐서 넘겨주는 방법으로 구현했다.

 

문제에 나온 첫 번째 예시로 예를 들어보면 

user_id	banned_id
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["fr*d*", "abc1**"]

user_id

frodo와 abc123을 선택하는 경우는 각각 인덱스가 0과 3이므로 "03"

fradi와 abc123을 선택하는 경우는 각각 인덱스가 1과 3이므로 "13"이 된다.

 

 

그리고 제재 아이디 목록은 순서가 상관없으므로 이 문자열을 정렬해준 후 set에 넣어줘서 중복을 제거해줬다.

최종적으로 set의 크기가 정답이 된다.

#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
bool check[8];
int blen, ulen;
set<string> s;
 
void solve(int index, string res, vector<string> user_id, vector<string> banned_id) {
    if (index == blen) {
        //불량 사용자의 아이디가 이벤트 응모자 아이디와 모두 매핑되어 제재목록이 다 만들어졌다면
        sort(res.begin(), res.end());
        s.insert(res);
        return;
    }
 
 
    string bid = banned_id[index];
    int bidlen = bid.size();
 
    //각 응모자 아이디와 index번째 불량 사용자 아이디를 비교한다.
    for (int i = 0; i < ulen; i++) {
        string uid = user_id[i];
 
        //이벤트 응모자 아이디와 불량 사용자 아이디의 길이가 다르다면 continue
        if (uid.size() != bidlen) continue;
        //i번째 응모아이디가 이미 불량 사용자의 아이디와 매핑된 경우 continue
        if (check[i]) continue;
 
 
        bool flag = true;
        //*을 제외한 문자들이 같은지 검사
        for (int j = 0; j < bidlen; j++) {
            if (bid[j] == '*') continue;
 
            //문자가 하나라도 다르면 매핑될 수 없다.
            if (uid[j] != bid[j]) {
                flag = false;
                break;
            }
        }
 
 
        //불량 사용자의 아이디와 별을 제외한 부분이 같은 경우
        if (flag) {
            //i번째 사용자 아이디는 index번째 불량아이디에 매핑된 것으로 체크하고 다음 불량아이디를 경우를 탐색한다.
            check[i] = true;
            solve(index + 1, res + to_string(i), user_id, banned_id);
 
            //index번째 불량 아이디에 매핑 될 수 있는 다른 사용자 아이디를 위해 현재 i번은 다시 false로 체크
            check[i] = false;
        }
    }
}
 
 
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
 
    ulen = user_id.size();
    blen = banned_id.size();
 
    solve(0, "", user_id, banned_id);
    answer = s.size();
 
    return answer;
}