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

링크

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

프로그래머스

풀이

 

당첨에서 제외되어야 할 제재 아이디 목록은 몇 가지 경우의 수가 가능한 지 구하는 문제이다.

 

user_id와 nanned_id 배열의 크기가 최대 8 이하 이므로

완전 탐색을 이용하여 모든 가능한 조합을 구해서 풀면 될 거 같았다.

 

그래서 dfs(백트래킹)

를 이용하여 하나씩 비교를 하도록 했다.

일단 user_id와 banned_id의 목록의 길이가 같아야 비교를 할 수 있고

길이가 같다면 문자열의 문자를 하나씩 비교하며 조건에 맞는지 확인하였다.

 

이렇게 모든 조합이 만들어지면 set에 추가하여 중복으로 만들어진 조합을 제거하였고

 

모든 탐색이 끝나면 조건에 맞는 모든 경우의 수가 들어 있기 때문에

set의 size를 출력해주어 답을 구할 수 있었다.

 

#include <string>
#include <vector>
#include<iostream>
#include<set>
#include<algorithm>
#define SIZE 10
using namespace std;

bool visited[SIZE];
set<string> _set;

void dfs(vector<string> user_id, vector<string> banned_id, int b_index) {
	int u_size = user_id.size();
	int b_size = banned_id.size();

   if (b_index >= b_size) {
      string res = "";
      for (int i = 0; i < user_id.size(); i++) {
         if (visited[i]) {
            res += i;
         }
      }
      _set.insert(res);
      return;
   }

 
   for (int i = 0; i < u_size; i++) {
      if (banned_id[b_index].size() != user_id[i].size() || visited[i]) {
         continue;
      }

      bool toggle = true;

      for (int j = 0; j < user_id[i].size(); j++) {
         if (banned_id[b_index][j] == '*') {
            continue;
         }
         if (user_id[i][j] != banned_id[b_index][j]) {
            toggle = false;
            break;
         }
      }

      if (toggle) {
         visited[i] = true;
         dfs(user_id, banned_id, b_index + 1);
         visited[i] = false;
      }
   }   
}
int solution(vector<string> user_id, vector<string> banned_id) {
   int answer = 0;
   dfs(user_id, banned_id, 0);
   answer = _set.size();
   return answer;
}