[프로그래머스] 불량 사용자 / 2019 카카오 개발자 겨울 인턴십 - JAVA

🔗 문제 링크

[프로그래머스] 불량 사용자 / 2019 카카오 개발자 겨울 인턴십

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

 

📝 풀이 과정

banned_id에 해당하는 아이디를 하나씩 고를 수 있는 조합을 찾는 문제이다.

 

banned_id에 존재하는 *을 .으로 변경한다면 쉽게 정규식을 사용이 가능하다. 이후, str.matches(pattern)을 사용해 문자열이 패턴과 일치 여부를 boolean값으로 받아올 수 있다.

 

조합을 모두 구했다고 하더라도 중복된 아이디들로 구성된 목록은 제거해주어야하는데 이를 비트마스킹 + Set의 조합으로 풀었다. 사용된 아이디의 인덱스로 비트를 마스킹해주고, 조합을 모두 구한다음 Set에 넣어주게 되면 알아서 중복을 제거해준다.

 

💻 코드

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {
    Set<Integer> set = new HashSet<>();
    String[] banPatterns;

    public int solution(String[] user_id, String[] banned_id) {
        banPatterns = Arrays.stream(banned_id)
                .map(b -> b.replace("*", ".")).toArray(size -> new String[size]);

        solve(0, 0, user_id);
        return set.size();
    }

    void solve(int idx, int visit, String[] userId) {
        if (idx == banPatterns.length) {
            set.add(visit);
            return;
        }

        for (int i = 0; i < userId.length; i++) {
            if ((visit & (1 << i)) > 0 || !userId[i].matches(banPatterns[idx])) continue;

            solve(idx + 1, visit | (1 << i), userId);
        }
    }
}