[프로그래머스 LV3] 불량 사용자 (C++)

https://school.programmers.co.kr/learn/courses/30/lessons/64064?language=cpp#

프로그래머스

 

순열 조합 백트래킹 문제라고 파악하는 것은 어렵지 않다.

그러나 문제의 핵심은 "어떤 사용자를 조합할 것인가?" 이 문장이 핵심이다.

 

ABCD , ABC, AB , BCD 사용자가 존재하고 밴 사용자로 **C, *** 가 있다고 예를 들어보자.

 

사용자들을 밴의 개수인 2개씩 조합하면

 

ABC, AB

ABC, BCD

ABCD, ABC

 

이런식으로 조합할 수 있다. 그리고 사용자로 모두 조합시키고 밴 사용자와 1대1 대응인지 체크하는 것은 쉽지 않다. 하나씩 대응시킨 다면 ABC 사용자는 **C, *** 를 모두 만족하기 때문에 어떤 것을 매칭시켜야할지 쉽지 않고 개수가 많아진다면 더더욱 어려워진다.

 

그래서 모든 사용자를 조합하면 안된다. 밴 사용자를 만족하는 사용자만 조합에 포함해야한다!

 

일반적인 조합 코드를 살펴보자.

 

void dfs(int idx, int cnt){
	if(idx == cnt) {
    	check
    }

    for(int i = idx; i < users.size(); i++){
        if(visited[i]) continue;
           visited[i] = true;
           dfs(idx + 1, cnt + 1);
           visited[i] = false;
    }
}

 

 

이렇게 하면 모든 사용자 조합을 구할 수 있다. 그러나 우리가 필요한 것은 각 밴을 만족하는 사람을 구해야한다.

 

1. 포문 안에 밴인지 아닌지 체크하는 함수가 하나 포함되어야한다. 

 

2. 각 밴 사용자는 하나의 사용자와만 대응되어야한다. 즉, ***, AB* 는 ABC라는 사용자에게 한번씩 대응되어야한다.

 

1번은 그냥 구현하면 되지만 2번을 만족하기 위해 잘 생각해보자. 지금 idx는 유저의 인덱스이다. 이러면 유저의 인덱스가 모든 밴 사용자 인덱스와 조합되게 된다. 다시말해 이중포문의 바깥을 유저 인덱스가 맡게 된다는 뜻으로 반대로 밴 사용자의 idx를 백트래킹의 idx로 사용한다.

 

이러면 ***의 인덱스인 0이

 

ABC, ABB, EDD 라는 사용자를 살펴보고 ABC에서 만족하므로 조합에 ABC를 포함하고 인덱스를 하나 늘려 AB*에 맞는 사용자를 찾게 되고 ABC는 visited가 true이므로 ABB를 살피게 되어 올바른 답을 하나 찾게 된다.

 

그래서 조합은 다음과 같이 만들어진다.

 

void dfs(int idx, int cnt){
    if(cnt == bans.size()){
        string tmp = "";
        
        for(int i = 0; i < users.size(); i++){
            if(visited[i]) tmp.push_back(i + '0');
        }
        
        answer.insert(tmp);
        
        return;
    }
    
    for(int i = 0; i < users.size(); i++){
        if(visited[i]) continue;
        if(check(users[i], bans[idx])){
            visited[i] = true;
            dfs(idx + 1, cnt + 1);
            visited[i] = false;
        }
    }
}

 

그리고 결국 순서대로 정답이 만들어지기 때문에 정렬할 필요 없이 셋에 지금까지의 조합을 넣어 set.size() 로 정답을 도출하였다.

 

조합이라는 간단한 솔루션에서 한 번더 응용하여 생각했어야하는 매우 좋은 문제라고 생각한다.

 

카카오의 레벨3 문제는 정말 탁월하다.

 

#include <string>
#include <vector>
#include <set>
using namespace std;

set<string> answer;
bool visited[8];

vector<string> users;
vector<string> bans;

bool check(string user, string ban){
    if(user.size() != ban.size()) return false;
    
    for(int i = 0; i < user.size(); i++){
        if(ban[i] == '*') continue;
        else if(ban[i] != user[i]) return false;
    }
    
    return true;
}

void dfs(int idx, int cnt){
    if(cnt == bans.size()){
        string tmp = "";
        
        for(int i = 0; i < users.size(); i++){
            if(visited[i]) tmp.push_back(i + '0');
        }
        
        answer.insert(tmp);
        
        return;
    }
    
    for(int i = 0; i < users.size(); i++){
        if(visited[i]) continue;
        if(check(users[i], bans[idx])){
            visited[i] = true;
            dfs(idx + 1, cnt + 1);
            visited[i] = false;
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) { 
    users = user_id;
    bans = banned_id;
    dfs(0,0);
    return answer.size();
}