[프로그래머스 Lv3] : 불량 사용자

문제 링크

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

프로그래머스

유저 아이디 목록과 일부가 지워진 제재 아이디 목록이 주어졌을 때,

가능한 제재 아이디 목록의 수를 리턴하는 문제.

 

풀이

제재 아이디의 일부가 가려져있기 때문에, 다양한 경우의 수가 만들어 질 수있다.

만약 주어진 제재 아이디가 "Fr*d*" 라면 "Frodo"로 가능하고 "Frida"  등등 조건을 만족하는 모든 아이디를 제재 가능하다.

심지어 "******" 처럼 모두 가려진 제재 아이디라면 글자수가 일치하는 모든 아이디를 제재할 수 있다.

이처럼 제재가 일대일 대응으로 이뤄지지 않기 때문에 경우의 수를 세기가 어려웠다.

 

그래서 일단 모든 경우의 수를 다 해보아야겠다고 생각했다.

먼저, 임의의 제재 아이디 i가 제재할 수 있는 유저 아이디의 목록을 따로 생성한다.

예제를 보면서 설명하자면

유저 아이디 목록이 ["frodo", "fradi", "crodo", "abc123", "frodoc"]

제재 아이디 목록이 ["fr*d*", "abc1**"] 라면

0번째 제재 아이디 "fr*d"가 제재 가능한 유저 아이디는 0번째 "frodo"와 1번째 "fradi" 두 가지가 가능하다.

1번째 제재 아이디 "abc1**" 은 3번째 유저 아이디인" abc123"를 제재할 수 있다.

그렇다면  can_ban[0] = {0, 1}, can_ban[1] = {3} 이렇게 된다.

같은 방식으로 모든 제재 아이디에 대해 제재 가능한 유저들의 번호를 저장한다.

 

이렇게 해서 모든 제재 아이디에 대해 제재할 아이디를 하나씩 대응시키는 방식이다.

이미 제재된 아이디는 방문체크를 해서 여러개의 제재 아이디가 하나의 유저아이디를 제재하지 않도록 했다.(일대일 대응)

모든 제재 아이디에 대해 하나씩 유저아이디를 하나씩 대응시켰다면 목록 하나가 완성된 것이다.

구현은 백트래킹을 이용해서 깊이가 모든 제재 아이디의 수와 같아졌을 경우 경우의 수를 하나 더하고 리턴시켰다.

 

여기서 한가지 문제가 발생한다.

만약 여러개의 제재 아이디가 중복적으로 같은 아이디를 제재할 수 있을 때, 중복이 발생한다.

"*****" 라는 제재 아이디와 "fr*d*" 라는 제재 아이디는 공통적으로 "frodo", "frida" 라는 아이디를 제재할 수 있다.

1. "*****" -> "frodo" , "fr*d*" -> "frida"

2. "*****" -> "frida" , "fr*d*" -> "frodo"

두 가지 경우는 다른 경우지만 결과만 놓고 본다면 제재된 아이디 목록은 같게 형성된다.

따라서 위와같은 중복을 제거해야했다.

팩토리얼을 이용해서 조합의 중복을 제거하면 될거라 생각했지만 아니었다.

 

결국 set을 이용해서 중복을 제거했다.

제거된 아이디 인덱스들을 정렬한 후 문자열로 바꿔 set에 집어넣었다.

만약 0, 1, 3번 아이디가 제재되었다고 하면 해당 번호들을 문자열로 이어붙여 "013"형태로 set에 넣는다

set은 중복을 알아서 제거해주기 때문에 최종적으로 set의 크기가 정답이 된다.

 

코드 작성

#include <string>
#include <vector>
#include <iostream>
#include <set>
#include <algorithm>
#include <string.h>
using namespace std;
const int MAX_N = 10;
bool visited[MAX_N];
set<string> cases;
void backtracking(int depth, vector<int> can_ban[], int n, int& answer, vector<int> list){
    if(depth == n){
        sort(list.begin(),list.end());
        string tmp = "";
        for(auto l : list)
            tmp += to_string(l);
        cases.insert(tmp);
        return;
    }
    for(int i = 0; i < can_ban[depth].size(); i++){
        if(visited[can_ban[depth][i]])
            continue;
        visited[can_ban[depth][i]] = true;
        list.push_back(can_ban[depth][i]);
        backtracking(depth + 1, can_ban, n ,answer, list);
        list.pop_back();
        visited[can_ban[depth][i]] = false;
    }
}
 
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    vector<int> can_ban[9]; //i번째 banned_id가 ban 가능한 유저 아이디 목록
    vector<int> temp;
    for(int i = 0; i<banned_id.size(); i++){
        for(int j = 0; j<user_id.size();j++){
            if(banned_id[i].length() != user_id[j].length())
                continue;
            bool chk = true;
            for(int com = 0; com < banned_id[i].length(); com++){
                if(banned_id[i][com] == '*')
                    continue;
                if(banned_id[i][com] != user_id[j][com]){
                    chk = false;
                    break;
                }
            }
            if(chk)
                can_ban[i].push_back(j);
        }
    }
    backtracking(0, can_ban, banned_id.size(), answer, temp);
    answer = cases.size();
    return answer;
}