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

문제

 

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

프로그래머스

문제풀이

 

모든 경우의 수를 탐색해 문제를 풀었다.

밴을 당한 아이디 기준으로 유저 아이디와 크기가 같은지, '*'을 제외하고 모두 같은지를 판별한다.

삼중 반복문이 끝났으면 밴을 당한 아이디를 모두 찾았을 것이다.

 

이제 그 아이디를 가지고 조합을 짜야한다.

조합을 짤 때 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리한다.

그리고 제제 목록에 같은 아이디가 여러 개 중복될 수는 없다.

 

조합을 짤 때는 DFS로 모든 경우를 탐색했다.

두 번의 set을 통해 중복을 제거했다.

DFS인자에 있는 set은 {frodo, frodo}의 경우를, answer의 set은 {frodo, crodo}, {crodo,  frodo}의 중복을 제거하기 위함이다.

 

코드

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

set<string>answer;
vector<vector<string>>banned_ids;

void DFS(int idx, set<string>ids) {
    int idx2(0), idx3(0);
    for (idx2 = 0; idx2 < banned_ids[idx].size(); ++idx2) {
        set<string>nids = ids;
        nids.insert(banned_ids[idx][idx2]);
        if (idx + 1 < banned_ids.size()) {
            DFS(idx + 1, nids);
        }
        else {
            string set_id("");
            if (nids.size() == banned_ids.size()) {
                for (auto iter = nids.begin(); iter != nids.end(); ++iter) {
                    set_id += *iter;
                }
                answer.insert(set_id);
            }
        }
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int idx(0), idx2(0), idx3(0);

    banned_ids = vector<vector<string>>(banned_id.size());

    for (idx = 0; idx < banned_id.size(); ++idx) {
        for (idx2 = 0; idx2 < user_id.size(); ++idx2) {
            if (banned_id[idx].size() != user_id[idx2].size()) continue;
            for (idx3 = 0; idx3 < user_id[idx2].size(); ++idx3) {
                if (banned_id[idx][idx3] == '*') continue;
                else if (banned_id[idx][idx3] != user_id[idx2][idx3]) break;
            }
            if (idx3 == user_id[idx2].size()) {
                banned_ids[idx].push_back(user_id[idx2]);
            }
        }
    }

    DFS(0, {});

    return answer.size();
}