[프로그래머스] Lv.3 불량 사용자.java

lv.3 불량 사용자.java

import java.util.*;

class Solution {
    String[] userIds;
    String[] bannedIds;
    boolean[] visited;
    HashSet<HashSet<String>> result = new HashSet<>();

    public int solution(String[] user_id, String[] banned_id) {
        userIds = user_id;
        bannedIds = banned_id;
        visited = new boolean[userIds.length];

        dfs(new HashSet<>(), 0);

        return result.size();
    }

    void dfs(HashSet<String> set, int depth) {
        if (depth == bannedIds.length) {
            result.add(set);
            return;
        }

        for (int i = 0; i < userIds.length; i++) {
            if (set.contains(userIds[i])) {
                continue;
            }

            if (check(userIds[i], bannedIds[depth])) {
                set.add(userIds[i]);
                dfs(new HashSet<>(set), depth + 1);
                set.remove(userIds[i]);
            }
        }
    }

    boolean check(String userId, String bannedId) {
        if (userId.length() != bannedId.length()) {
            return false;
        }

        boolean match = true;
        for (int i = 0; i < userId.length(); i++) {
            if (bannedId.charAt(i) != '*' && userId.charAt(i) != bannedId.charAt(i)) {
                match = false;
                break;
            }
        }

        return match;
    }
}

이 코드는 DFS (Depth-First Search) 알고리즘을 이용하여 가능한 조합을 모두 찾아내는 문제입니다.

먼저, solution 메소드에서는 dfs 메소드를 호출합니다. dfs 메소드는 set과 depth라는 두 개의 매개변수를 받습니다. set은 현재까지 선택된 사용자 ID의 집합이고, depth는 현재 탐색하는 banned_id의 인덱스를 나타냅니다.

만약 depth가 banned_id의 길이와 같다면, 즉, 가능한 조합을 모두 선택한 경우라면, 이때의 set을 result에 추가하고 dfs 메소드를 종료합니다.

그렇지 않은 경우, for 반복문을 통해 user_id 배열의 모든 요소를 탐색합니다. 이때, set에 이미 선택된 사용자 ID가 포함되어 있다면, 해당 사용자 ID는 제외합니다.

그리고 check 메소드를 호출하여, 해당 사용자 ID가 현재 탐색 중인 banned_id와 일치하는지 확인합니다. 만약 일치한다면, 해당 사용자 ID를 set에 추가하고 dfs 메소드를 재귀호출합니다. 이때 set을 매개변수로 넘길 때, HashSet 클래스의 생성자를 호출하여 새로운 객체를 생성하여 넘겨줍니다. 이유는 set을 그대로 사용하면 기존에 선택된 사용자 ID를 변경할 수 있기 때문입니다.

dfs 메소드가 재귀호출에서 되돌아오면, set에서 해당 사용자 ID를 제거합니다.

check 메소드는 사용자 ID와 금지된 ID가 일치하는지 확인하는 메소드입니다. 먼저, 두 문자열의 길이가 다르다면 일치하지 않으므로 false를 반환합니다. 그리고 각 문자열의 문자를 하나씩 비교하면서, 금지된 ID의 해당 문자가 '*'이 아니고, 사용자 ID의 해당 문자와 다르다면 일치하지 않으므로 false를 반환합니다. 그렇지 않은 경우, 모든 문자가 일치하므로 true를 반환합니다.

마지막으로, result의 크기를 반환하여 가능한 조합의 개수를 구합니다. 이때, result는 HashSet 클래스를 이용하여 중복을 허용하지 않도록 구현되어 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges