알고리즘(C++) / 프로그래머스 level 3 : 불량 사용자

level 3 : 불량 사용자

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

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

 

코드

//프로그래머스 불량 사용자
#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

bool visited[8];
set<string> s; //중복 포함 x

void DFS(vector<string>& user_id, vector<string>& banned_id, int index) {
    if (index == banned_id.size()) {
        string st;
        for (int i = 0; i < user_id.size(); i++) {
            //제재아이디 조합
            if (visited[i] == true)
                st += user_id[i];
        }
        s.insert(st); //추가
        return;
    }

    for (int i = 0; i < user_id.size(); i++) {
        //이전 탐색한 경우
        if (visited[i] == true)
            continue;
        //아이디 길이가 다를 경우
        if (user_id[i].size() != banned_id[index].size())
            continue;
        
        bool check = true;
        for (int j = 0; j < user_id[i].size(); j++) {
            if (banned_id[index][j] == '*') {
                continue;
            }
            //같지 않을 경우 false
            if (banned_id[index][j] != user_id[i][j]) {
                check = false;
                break;
            }
        }
        if (check == true) {
            visited[i] = true; //방문
            DFS(user_id, banned_id, index + 1);
            visited[i] = false; //방문 x
        }
    }
}

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

int main() {
    vector<string> user_id = { "frodo", "fradi", "crodo", "abc123", "frodoc" };
    vector<string> banned_id = { "fr*d*", "abc1**" };
    cout << solution(user_id, banned_id) << "\n";
    return 0;
}

 

설명

이번 문제는 재귀함수로 구현할 수 있다. banned_id와 일치하는 제재 아이디를 구하고 다음 banned_id와 일치하는 제재 아이디를 구하면서 반복할 수 있다. 제재 아이디를 banned_id의 갯수만큼 구하였다면 아이디의 조합을 string으로 저장하여 set에 추가할 수 있다. 여기서 set은 중복을 포함하지 않는다. 따라서 중복되는 경우는 제외할 수 있다. 또한 visited 배열을 이용하여 이전에 제재 아이디를 구하였다면 다음 제재 아이디는 이전에 구한 제재 아이디를 제외하고 구할 수 있다. 재귀함수를 이용하여 모든 조합을 찾아낼 수 있다. 

 

고찰

이번 문제는 혼자 풀지 못했다 조금만 더 생각하면 혼자 풀 수 있었을거 같은데.. 아쉽다...

구글링해보니 재귀함수로 푼다는 것을 알 수 있었다. 차근차근 하나씩 생각하고 반복되는 부분을 찾으면 쉽게 구현할 수 있을거 같다. 

 

참고

https://algosu.tistory.com/48