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

📌 Problem

사용자의 ID는 알파벳 소문자와 숫자로만 이루어져 있으며 중복되는 ID는 없다. 이벤트에 응모한 전체 사용자 ID 배열과 비정상적인 방법으로 이벤트에 응모하여 제한된 사용자 ID 배열이 주어진다. 이 때 비정상적인 방법으로 이벤트에 응모한 사용자 ID들은 최소 1개 이상의 문자가 *으로 가려져 있다. 예를 들어, codesver이라는 사용자 ID는 co*es*er과 같이 아이디가 가려져 있다. 제한된 사용자 ID 배열으로 유추할 수 있는 제한 서로 다른 사용자 집합의 수를 구하여 반환한다.

📌 Solution

다음의 예시를 바탕으로 설명한다.

전체 사용자 ID	: ["frodo", "fradi", "crodo", "abc123", "frodoc"]
제한된 사용자 ID	: ["fr*d*", "*rodo", "******", "******"]

1. 제한된 사용자 ID와 매칭이 되는 모든 사용자 ID 번호(Index) 리스트를 구한다.

fr*f*	: [ 0, 1 ]
*rodo	: [ 0, 2 ]
******	: [ 3, 4 ]
******	: [ 3, 4 ]

2. 백트래킹으로 조합할 수 있는 모든 경우의 수를 구하고 각 경우를 bit masking 한다.

fr*d*	*rodo	******	******	Bit Masking
0	2	3	4	11101
0	2	4	3	11101
1	0	3	4	11011
1	0	4	3	11011
1	2	3	4	11110
1	2	4	3	11110

3. Bit masking 된 정수들은 Set 저장이되며 최종적으로 Set의 크기가 정답이다.

📌 Code

class Solution {

    private final Set<Integer> bannedSet = new HashSet<>();

    public int solution(String[] userId, String[] bannedId) {
        List<List<Integer>> matchedUsers = matchBannedId(userId, bannedId);
        boolean[] matched = new boolean[userId.length];
        match(matchedUsers, matched, 0);
        return bannedSet.size();
    }

    private List<List<Integer>> matchBannedId(String[] userId, String[] bannedId) {
        return new ArrayList<>() {{
            for (String bannedUser : bannedId) {
                bannedUser = bannedUser.replace('*', '.');
                List<Integer> users = new ArrayList<>();
                for (int uid = 0; uid < userId.length; uid++)
                    if (userId[uid].matches(bannedUser)) users.add(uid);
                if (!users.isEmpty()) add(users);
            }
        }};
    }

    private void match(List<List<Integer>> matchedUsers, boolean[] matched, int bid) {
        if (bid >= matchedUsers.size()) {
            int bits = 0;
            for (boolean flag : matched) {
                bits = bits << 1;
                if (flag) bits |= 1;
            }
            bannedSet.add(bits);
        } else for (int uid : matchedUsers.get(bid)) {
            if (!matched[uid]) {
                matched[uid] = true;
                match(matchedUsers, matched, bid + 1);
                matched[uid] = false;
            }
        }
    }
}