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

코딩테스트 연습 - 불량 사용자 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 불량 사용자

어떻게 생각하고 문제를 풀었는가?

불량 사용자 아이디의 탐색은 길이가 같아야 합니다.

*문자를 0~9, a~z의 문자 탐색이 가능하도록 정규표현식 \w로 변경하여 문자의 탐색을 수행하여 일치하는 아이디들을 찾을 수 있습니다.

주어진 조건에서 순서에 상관없이 아이디 목록이 동일하다면 동일한 케이스로 인식됩니다.

이를 해결하고자 중복을 방지하는 HashSet에 주어진 문자열 배열에서 어떤 아이디를 선택했는지 저장하고자 하였습니다.

코드

import java.util.*;
class Solution {
    String[] regex;
    HashSet<Integer> set = new HashSet<>();
    public int solution(String[] user_id, String[] banned_id) {
        regex = new String[banned_id.length];
        for(int i=0; i<banned_id.length; i++){
            regex[i] = banned_id[i].replace("*", "[\\w]");
        }
        dfs(0,user_id,0);
        
        return set.size();
    }
    void dfs(int index, String[] user_id, int bit){
        if(index==regex.length){
            set.add(bit);
            return;
        }
        for(int i=0; i<user_id.length; ++i) {
            if((((bit>>i) & 1) != 1) && user_id[i].matches(regex[index])){
                dfs(index+1, user_id, bit|1<<i);
            }
        }
    }
}

주어지는 user_id의 크기를 확인하지 않고 어떤 아이디가 사용되었는지 기억하고자 bitmasking을 활용하였습니다.

해당 아이디를 사용했다면 user_id의 인덱스위치에 있는 bit값을 1로 변경함으로써 어떤 인덱스의 아이디를 선택했는지 기억할 수 있고, 모든 불량 사용자 정보에 대해 선택이 이루어졌다면 bit조합을 HashSet에 저장함으로써 중복 없는 모든 경우를 확인할 수 있습니다.