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

https://programmers.co.kr/learn/courses/30/lessons/64064

 

🐢 설명

총 사용자의 id N개 중에서 id의 부분 문자가 *처리된 R개의 ban Id를 알고 있을 때, 몇개의 id 조합이 나올 수 있는지 묻는 문제이다.

 

조합 : N개 중에서 순서에 상관없이 R개를 뽑을 수 있는 경우의 수

 

id가 ABC, DEF 가 있을 때, [ABC, DEF] 의 경우나 [DEF, ABC]의 경우는 같다는 것이다. 따라서 nCr로 조합을 모두 확인하면서 [*] 처리에 대해 포함되는 아이디인지 확인하면 된다.

 

1. list에 id를 순서대로 넣는다.
2. id 담은 개수가 밴 아이디 개수와 같다면 해당 아이디들이 밴 아이디와 같은지 유효성 검사를 한다. (func : checkBanId)
3. 담은 모든 id에 대해서 해당 id와 매칭되는 ban Id가 있는지 확인.
   • 있다면 해당 ban Id는 제외하고 다른 id들을 이어서 비교한다.
   • 없다면 뽑은 리스트 자체가 문제가 있는 것이므로 바로 종료하고 다른 조합으로 다시 뽑는다.
4. 모두 ban id와 매칭이 된 경우 아이디들을 정렬해서 문자열로 만들고 중복 없이 set에 담아줬다.
5. set의 크기가 가능한 조합의 개수로 반환했다.

 

🐢코드

import java.util.*;

class Solution {
    static boolean[] visited;
    static String[] userIds;
    static String[] banIds;
    static boolean[] used;
    static HashSet<String> idSet = new HashSet<>();
    
    public int solution(String[] user_id, String[] banned_id) {
        
        userIds = user_id;
        banIds = banned_id;
        
        // nCr 조합
        
        int N = user_id.length;
        int R = banned_id.length;
        visited = new boolean[N];
        
        comb(0, 0, N, R, new LinkedList<Integer>());
        
        return idSet.size();
    }
    
    private static void comb(int idx, int select, int n, int r, LinkedList<Integer> banIdList)
    {
        if (select == r)
        {
            used = new boolean[r];
            int count = 0;
            ArrayList<String> idList = new ArrayList<>();
            
            for (int i : banIdList) {
                idList.add(userIds[i]);

                boolean flag = false;
                for (int j = 0; j < r; j++) {
                    if (!used[j] && checkBanId(userIds[i], banIds[j])) {
                        used[j] = true;
                        flag = true;
                        break;
                    }
                }
                if (!flag) return;
                else count++;
            }
            
            if (count == r) {
                Collections.sort(idList);
                
                StringBuilder idStr = new StringBuilder();
                for (String id : idList) idStr.append(id);
                
                if (!idSet.contains(idStr.toString()))
                    idSet.add(idStr.toString());
            }
        }
        
    
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                banIdList.add(i);
                comb(i + 1, select + 1, n, r, banIdList);
                visited[i] = false;
                banIdList.pollLast();
            }
        }
    }
    
    private static boolean checkBanId(String id, String banId) {
        if (id.length() != banId.length()) return false;
        
        for (int i = 0; i < banId.length(); i++)
        {
            char c = banId.charAt(i);
            
            if (c == '*') continue;
            else if (id.charAt(i) != c) {
                return false;
            }
        }
        return true;
    }
}

 

🐢 마무리