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

문제출처

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

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

 

문제풀이

정규표현식과 완전탐색으로 풀이하면 되는 문제입니다. DFS시 저는 bitmask를 visit배열 대신 사용해서 풀이했습니다. 

문제를 풀이할때 제가 생각한 알고리즘은 다음과 같습니다.

 

1. *문자를 정규표현식에 맞게 .로 치환

2. pattern과 matcher를 사용해 응모자 아이디와 매칭되는지 판단

3. 매칭이 된다면 길이가 같은지 판단

4. 이미처리한 사항(방문한 사항)이라면 건너뛰고 처리하지 않았다면 dfs함수를 호출

5. banned_id와 지금까지 찾아낸 제제된 아이디의 사이즈(bannedIdSize)가 같다면 set에 추가

6. 중복없는 set의 사이즈를 반환

 

비트마스크가 익숙하지 않은 분이면 아래 포스팅을 참고하시면 도움이 되실겁니다.

2019/01/28 - [Algorithm 이론] - [Bitmask] 비트마스크 기초

[Bitmask] 비트마스크 기초

레벨3문제인데 개인적으로 어렵게 풀이한 문제였습니다. 정규표현식과 비트마스크 개념을 다시 확인할 수 있던 문제

 

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/Programmers/%EC%B9%B4%EC%B9%B4%EC%98%A4%20-%20%EB%B6%88%EB%9F%89%20%EC%82%AC%EC%9A%A9%EC%9E%90.java

sw93/algorithm

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

// * 문자 . 로 치환
// Pattern matcher를 사용해 해당되는 문자인지 판단
// 해당된다면 길이도 같은지 확인하고 이미 추가한 아이디가 아니라면 set에 추가
class Solution {
    private static HashSet<Integer> set;
    public int solution(String[] user_id, String[] banned_id) {
        set = new HashSet<>();
        dfs(user_id, banned_id, 0, 0, 0);
        return set.size();
    }
    
    private static void dfs(String[] user_id, String[] banned_id, int index, int bannedIdSize, int visitBit) {
        if (bannedIdSize == banned_id.length) {
            set.add(visitBit);
            return;
        }
        
        for (int i=0; i<user_id.length; i++) {
            String changeBannedId = banned_id[index].replace("*", ".");
            Pattern pattern = Pattern.compile(changeBannedId);
            Matcher matcher = pattern.matcher(user_id[i]);
            
            // 정규 표현식에 매칭되고 길이가 같으면
            if (matcher.find() && user_id[i].length() == banned_id[index].length()) {
                
                // 이미 방문한 것은 건너뜀
                if ((visitBit & (1<<i)) == 1<<i) continue;
                dfs(user_id, banned_id, index+1, bannedIdSize+1, (visitBit | (1<<i)));
            }
        }
    }
}