[프로그래머스/DFS] Lv.3 불량 사용자 : Java (Feat. 비트마스크로 개선하기)

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/64064

 

1. 문제를 풀면서 막혔던 지점

이 문제의 핵심은 단순 DFS가 아니라 “중복 제거”였다.

예를 들어 이런 경우:

[0, 1]
[1, 0]

이 두 개는 서로 다른 탐색 결과지만, 이 문제에서는 같은 경우로 취급해야 한다.

---

2. 처음 접근 (배열 기반)

처음에는 이렇게 풀었다.

boolean[] selected;
int[] result;

그리고 DFS를 돌리면서

selected[idx] = true;
result[depth] = idx;
dfs(depth + 1);
selected[idx] = false;

result에 우선 선택된 사용자 인덱스를 저장했다.

 

그래서 정렬 후, 문자열로 변환해서 Set 성질을 이용해 중복 제거를 했다.

---

3. 비트마스크 적용

예를 들어 user가 4명이라면:

index: 0 1 2 3

선택 상태를 이렇게 표현할 수 있다:

0101 → 0번, 2번 선택

 

이 비트마스크를 이용해 선택된 사용자의 정보를 저장하는 것이다.

그럼 굳이 선택된 user를 저장하는 boolean[] 배열과 result[] 배열을 쓰지 않아도 된다!!

1) 선택 여부 확인

(bit >> idx) & 1

idx번째 비트가 1인지 확인

2) 선택하기

bit | (1 << idx)

idx번째 user 선택

 

 

4. 문제 풀이 코드

물론 findUsers 함수를 아래와 같이 더 간단하게 풀어낼 수 있다.

String reg = banned_id[index].replace("*", "[\\w\\d]");

!user_id[i].matches(reg)

 

import java.util.*;

class Solution {
    private List<Integer>[] candidates;
    private Set<Integer> results;
    private int bannedDepth;

    public int solution(String[] user_id, String[] banned_id) {
        bannedDepth = banned_id.length;
        candidates = new ArrayList[bannedDepth];
        results = new HashSet<>();

        for (int i = 0; i < bannedDepth; i++) {
            candidates[i] = new ArrayList<>();
            findUsers(i, banned_id[i], user_id);
        }

        dfs(0, 0);

        return results.size();
    }

    private void dfs(int depth, int bit) {
        if (depth == bannedDepth) {
            results.add(bit);
            return;
        }

        for (int idx : candidates[depth]) {
            if (((bit >> idx) & 1) == 1) continue;

            dfs(depth + 1, bit | (1 << idx));
        }
    }

    private void findUsers(int idx, String banned, String[] user_id) {
        for (int i = 0; i < user_id.length; i++) {
            if (isMatch(banned, user_id[i])) {
                candidates[idx].add(i);
            }
        }
    }

    private boolean isMatch(String banned, String user) {
        if (banned.length() != user.length()) return false;

        for (int i = 0; i < banned.length(); i++) {
            char b = banned.charAt(i);

            if (b == '*') continue;
            if (b != user.charAt(i)) return false;
        }

        return true;
    }
}