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

1. 문제 풀이 아이디어

• 매칭된 사용자의 인덱스를 저장한 후, 모든 가능한 조합을 찾아 Set에 저장하여 문제를 해결한다.

2. 나의 정답 코드

class Solution {
    List<Integer>[] list;
    Set<Integer> set = new TreeSet<>();
    Set<String> resultSet = new HashSet<>();
 
    public int solution(String[] user_id, String[] banned_id) {
        list = new List[banned_id.length];
        for (int i = 0; i < banned_id.length; i++) {
            list[i] = new ArrayList<>();
            Pattern p = Pattern.compile(banned_id[i].replace("*", "."));
            for (int j = 0; j < user_id.length; j++) {
                Matcher m = p.matcher(user_id[j]);
                if (m.matches()) {
                    list[i].add(j);
                }
            }
        }
        check(0);
        return resultSet.size();
    }

    private void check(int n) {
        if (n == list.length) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int i : set) {
                stringBuilder.append(i);
            }
            resultSet.add(stringBuilder.toString());
            return;
        }
        for (int i = 0; i < list[n].size(); i++) {
            set.add(list[n].get(i));
            if (set.size() != n + 1) continue;
            check(n + 1);
            set.remove(list[n].get(i));
        }
    }
}

3. 정리

• 금지된 아이디를 순회하며 Pattern과 Matcher를 사용해 매칭된 사용자 아이디의 인덱스를 리스트에 저장한다.

• check 메서드에서 재귀를 통해 DFS로 탐색하며 가능한 조합을 set에 저장한다.

• 최대 깊이에 도달하면 현재 조합을 문자열로 변환하여 resultSet에 추가해 중복을 제거한다.

• 탐색이 완료된 후, 고유한 조합의 개수를 반환해 문제를 해결한다.