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

💡 풀이

✔️ 순열 + TreeSet

• 순열 알고리즘으로 id들 중 불량 id 수대로 뽑음
• 뽑은 id를 불량 id와 매칭
• 일치하면 treeSet에 담아서 정렬하면서 set으로 저장
• 뽑은 id가 불량 id와 맞다면 treeSet의 사이즈가 불량 id 수와 같아야함
• 같으면 hashSet인 answerSet에 treeSet 그대로 넣기
  => ["frodo", "crodo"]와 ["crodo", "frodo"]은 하나로 저장해야하기 때문

import java.util.*;

class Solution {
    static Set<TreeSet<String>> answerSet = new HashSet<>();
    public int solution(String[] user_id, String[] banned_id) {
        String[] output = new String[banned_id.length];
        permutation(output, 0, user_id, banned_id, new boolean[user_id.length]);
        return answerSet.size();
    }
    
    // 순열 알고리즘
    public void permutation(String[] output, int depth, String[] user_id, String[] banned_id, boolean[] visited){
        if(depth == banned_id.length){
            TreeSet<String> idSet = new TreeSet<>();
            for(int i = 0; i<banned_id.length; i++){
                // 순열로 뽑은 id와 불량 id가 동일한지 확인
                // 동일하면 treeSet에 넣기
                if (check(output[i], banned_id[i])){
                    idSet.add(output[i]);
                } 
                
            }
            // 동일한 id를 담은 idSet의 길이가 불량 id 수와 동일하면 
            // answerSet에 treeMap 형태 그대로
            if (idSet.size() == banned_id.length) {
                answerSet.add(idSet);
            }       
            return;
        }
        
        for(int i = 0; i<user_id.length; i++){
            if (!visited[i]){
                visited[i] = true;
                output[depth] = user_id[i];
                permutation(output, depth+1, user_id, banned_id, visited);
                visited[i] = false;
            }
        }
    }
    
    // 순열로 뽑은 id와 불량 id가 매칭되는지 확인
    public boolean check(String output, String banned_id){ 
        if (output.length() != banned_id.length()) return false;
        for(int i = 0; i<output.length(); i++){
            if (banned_id.charAt(i) == '*') continue;
            if (output.charAt(i) != banned_id.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

🫥 처음에는 조합으로 고르고 어떻게 매칭할지를 계속 고민했음. 그냥 순열로 처음부터 뽑고 그대로 매칭시켜보면 해결됐던 문제!!