[프로그래머스 / Level3] 불량 사용자 (Java)

문제 보기

사용한 것

• 불량 사용자 후보군 리스트의 경우의 수를 구하기 위한 백트래킹

풀이 방법

• 불량 아이디 별로 조건에 만족하는 아이디를 HashSet에 넣어준다.
• 이 때 서로 같은 메모리를 가리키지 않도록 매 단계마다 깊은 복사한다.
• 모든 불량 아이디가 채워지면 result에 담는다.
• result.size()를 반환한다.

코드

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;
    }
}