EunSung.log

불량 사용자

4 min read

문제 정보

풀이

user_id, banned_id 배열과 각 원소의 크기가 크지 않기 때문에 완전 탐색해도 무방하다.

banned_id[i]에 대해 user_id를 DFS로 순회 및 백트래킹한다.

  • boolean[] visited를 통해 이미 선택된 ID는 선택하지 않는다.
  • 백트래킹을 통해 가능한 모든 조합을 탐색한다.

banned_id의 조합이 같더라도 순서만 다르면 중복으로 집계될 수 있다. 예를 들어 {user_1, user_2}와 {user_2, user_1}은 같은 조합이지만 DFS 탐색 순서에 따라 다른 결과로 처리될 수 있다.

이를 방지하기 위해 선택된 user_id의 조합을 비트마스크로 표현한다. user_id의 각 인덱스를 비트 하나에 대응시켜, 선택된 user_id 조합을 하나의 정수로 표현하는 방식이다.

예를 들어, user_id = {"a", "b", "c", "d", "e"]일 때, 0번째와 2번째 유저가 선택되었다면 비트마스크는 가 된다.

bitmask | (1 << i)

1 << i는 i번째 비트만 1인 값이고, 이를 bitmask에 OR 연산하면 i번째 비트를 1로 설정한다. 즉, i번째 user_id가 선택되었음을 기록하는 것이다.

이렇게 하면 {0번, 2번} 순서로 선택된 조합과 {2번, 0번} 순서로 선택된 조합 모두 동일한 비트마스크 값 5를 가지므로, Set에 저장할 때 중복이 제거된다.

이하는 입출력 예시 2의 경우로 든 예시다.

dfs(0, 0)
	├── frodo 선택 -> dfs(1, 1)
	│	  ├── crodo 선택 -> dfs(2, 0101)
	│	  │	    ├── abc123 선택 -> dfs(3, 1101) -> HashSet.add(13)
	│	  │     └── frodoc 선택 -> dfs(3, 10101) -> HashSet.add(21)
	│	  │
	│	  └── 여기서 frodo 선택은 하지 않음 (∵ 이 시점에 visited[0] = true)
	│
	│
백트래킹 (visited[0] = false)
	│
	└── crodo 선택 -> dfs(1, 0100)                     ┐
		  └── frodo 선택 -> dfs(2, 0101)               │=> 추가 안됨 (∵ Set)
				  ⋮

코드

import java.util.*;
 
class Solution {
    private Set<Integer> result = new HashSet<>();
    boolean[] visited;
    String[] userId;
    String[] bannedId;
    
    public int solution(String[] user_id, String[] banned_id) {
        userId = user_id;
        bannedId = banned_id;
        visited = new boolean[user_id.length];
        
        dfs(0,0);
        
        return result.size();
    }
    
    private void dfs(int bannedIdx, int bitmask) {
        if (bannedIdx == bannedId.length) {
            result.add(bitmask);
            return;
        }
        
        for (int i = 0; i < userId.length; i++) {
            if (visited[i]) 
                continue;
            if (!isMatch(userId[i], bannedId[bannedIdx]))
                continue;
            
            visited[i] = true;
            dfs(bannedIdx + 1, bitmask | (1 << i));
            visited[i] = false;
            
        }
    }
    
    private boolean isMatch(String userId, String bannedId) {
        if (userId.length() != bannedId.length())
            return false;
        
        for (int i = 0; i < userId.length(); i++) {
            if (bannedId.charAt(i) == '*')
                continue;
            if (userId.charAt(i) != bannedId.charAt(i))
                return false;
        }
        
        return true;
    }
}

백링크