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

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

문제

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

문제 분석

조건

불량 사용자 목록이 주어진다. 불량 사용자 아이디의 일부 문자가 `*`로 마스킹된 형태로 주어질 때, 사용자 아이디 중 불량 사용자 목록에 주어진 패턴들과 매칭될 수 있는 유저 아이디조합의 경우의 수를 구하는 문제이며, 같은 조합의 경우 1가지로 계산한다.

풀이방법

`banned_id`에 포함된 `*`문자를 `.`으로 바꾸어 정규표현식을 활용할 수 있도록 하였다. 조합을 구할 때처럼 user_id 중 정규식에 맞는 조합으로 탐색하였으며 중복된 조합을 제거하기 위해 `Set`을 사용하였다.

코드

import java.util.*;

class Solution {
    static Set<String> answerSet = new HashSet<>(); // 중복 조합 방지를 위한 Set
    static boolean[] checks;    // 조합에 들어간 단어 체크

    public int solution(String[] user_id, String[] banned_id) {

        for (int i = 0; i < banned_id.length; i++) {
            // 정규식 활용을 위한 문자 변환
            banned_id[i] = banned_id[i].replace('*', '.');
        }
        checks = new boolean[user_id.length];
        combination(0, new String[banned_id.length], banned_id, user_id);

        return answerSet.size();
    }

    /**
     * 단어 조합을 만드는 함수
     *
     * @param depth
     * @param combi
     * @param bannedIds
     * @param userIds
     */
    private void combination(int depth, String[] combi, String[] bannedIds, String[] userIds) {
        if (depth == bannedIds.length) {
            // 분량 사용자 수만큼 아이디를 찾으면 해당 답을 Set에 넣기 위해 정렬한다.
            // 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리 < 문제 조건
            String[] answer = Arrays.copyOf(combi, combi.length);
            Arrays.sort(answer);
            answerSet.add(Arrays.toString(answer));
            return;
        }
        for (int i = 0; i < userIds.length; i++) {
            if (userIds[i].length() != bannedIds[depth].length()
                    || checks[i]) { // 문자열 길이와 이미 사용한 아이디인지 체크
                continue;
            }
            if (userIds[i].matches(bannedIds[depth])) {
                checks[i] = true;
                combi[depth] = userIds[i];
                combination(depth + 1, combi, bannedIds, userIds);
                checks[i] = false;
            }
        }
    }
}