[lv3] 불량 사용자

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

 

인접리스트 + set + 비트마스킹으로 풀었다.

 

1. 조합 혹은 순열을 뽑고, 아이디를 매칭하면 매 순간 아이디를 비교해야 하므로 비효율적이다.

(문제에서 주어지는 변수가 매우 작으므로 가능하긴 하다.)

그래서, 처음부터 banned_id 아이디에 포함되는 user_id를 인접리스트에 key값으로 저장한다.

 

2. 경우의 수를 구하는 법

 

[1번] [2번] [3번]

 A       A       B

 B      B      D

 C

 

후보군의 선택지는 다음 형태와 같다.

각 번호는 모두 하나의 알파벳이 할당되어야 하며, 알파벳을 중복하여 사용할 수 없다.

 

1번에 A,B를 선택하면 2번의 경우의 수에 영향을 미치고 C를 선택하면 미치지 않는다.

이는 3, ..., n번에 까지도 마찬가지이므로, 수학 공식으로 풀이하기엔 모든 조건 분기를 고려해야 하므로 어렵다.

 

따라서 완전탐색한다. 방문 체크 배열로 각 원소를 사용했는지를 기록하며 dfs 한다.

 

3. 순서 고려 , 중복 제거

 

문제에서, A B D와 B A D는 같은 경우로 취급한다. 이를 처리하기 위해 배열이나 리스트 등을 쓴다면 매 탐색마다 size()만큼 복잡도가 추가된다.

 

이는 비트마스킹으로 해결하였다. user_id <= 8 이므로 가능하며, 순서에 상관없이 값을 비교할 수 있다.

 

앞서 방문 체크 배열은 가지치기를 위함이고, 중복인 경우는 여전히 제거하지 못한다. 따라서 set을 사용하고 답으로 set.size()를 리턴한다.

 

import java.util.*;

class Solution {

    static Set<Integer> ansSet = new HashSet<>();
    static List<List<Integer>> match = new ArrayList<>();
    static int ul, bl;
    static boolean[] vst;
    public int solution(String[] user_id, String[] banned_id) {
        ul = user_id.length;
        bl = banned_id.length;

        for(int i=0; i<bl; i++) {
            match.add(new ArrayList<>());
        }

        for(int i=0; i<bl; i++) {
            for(int j=0; j<ul; j++) {
                List<Integer> banList = match.get(i);

                if(isbanned(user_id[j], banned_id[i]))
                    banList.add(j);
            }
        }

        vst = new boolean[ul];
        search(0, 0);

        return ansSet.size();
    }

    public static boolean isbanned(String user_name, String banned_name) {

        if(user_name.length() != banned_name.length()) return false;

        for(int i=0; i<user_name.length(); i++) {
            char uc = user_name.charAt(i);
            char bc = banned_name.charAt(i);

            if(bc != '*' && bc != uc) return false;
        }

        return true;
    }

    public static void search(int dep, int uBit) {
        if(dep == bl) {
            ansSet.add(uBit);
            return;
        }

        List<Integer> banList = match.get(dep);
        for(int i=0; i<banList.size(); i++) {
            int now = banList.get(i);
            if(!vst[now]) {
                vst[now] = true;
                search(dep + 1, uBit | (1 << now));
                vst[now] = false;
            }
        }
    }
}