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

프로그래머스 level 3 불량 사용자

카카오 문제다!!

 

소요시간 1시간..? 시간을 제대로 안봐서 사실 확실하지 않다..

---

전역 list 역할 : 찾은 경우의 수가 어떤 id 를 가지고 있는 지 넣어놓고 순서만 다르고 같은 id 가 있는 결과가 나오면 경우의 수를 추가하지 않을 수 있게 함

 

dfs함수의 매개변수

cnt : banned_id에서 몇 번째 아이디 검사 차례인지

selected : user_id에서 선택된 id

set : 경우의 수에서 선택된 id

 

현재 찾아야하는 banned_id의 길이를 구하고

모든 user_id 를 보면서 조건에 맞는 user_id를 찾아서 set에 추가하고 다음 banned_id 로 dfs() 재귀 돌림

cnt == N 이 되면 모든 banned_id 를 찾았다는 뜻이고

그 때 이미 찾은 경우의 수를 list에서 검사하여 같은 set이 있으면 경우의 수를 추가하지 않는다.

같은 set이 없으면 경우의 수 추가하고 list에 추가하여

다음 재귀 때 검사할 수 있도록 한다.

static String[] user, banned;
public int solution(String[] user_id, String[] banned_id) {
  N = banned_id.length;
  user = user_id;
  banned = banned_id;

  dfs(0, new boolean[user.length], new HashSet<>());

  return answer;
}

static int N, answer = 0;
static List<Set<String>> list = new ArrayList<>();
public void dfs(int cnt, boolean selected[], Set<String> set) {
  if(cnt == N) {
    for(Set<String> newSet : list) {
      if(newSet.containsAll(set)) {
      	return;
      }
    }

    list.add(set);
    answer++;
    return;
  }

  int ban_len = banned[cnt].length();
  for (int j = 0; j < user.length; j++) {
    if(selected[j]) continue;
    if(ban_len != user[j].length()) continue;

    boolean same = true;
    for (int k = 0; k < ban_len; k++) {
      if(banned[cnt].charAt(k) == '*') continue;
      if(banned[cnt].charAt(k) != user[j].charAt(k)) {
        same = false;
        break;
      }
  	}
    if(same) {
      boolean[] copy = new boolean[user.length];
      for (int k = 0; k < copy.length; k++) {
          copy[k] = selected[k];
      }
      copy[j] = true;
      Set<String> copySet = new HashSet<>();
      for(String s : set) {
          copySet.add(s);
      }
      copySet.add(user[j]);
      dfs(cnt+1, copy, copySet);
     }
   }

}