[Java] 프로그래머스 : 불량 사용자*

1. 문제

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

프로그래머스

 

 

 

2. 풀이 과정

요약 : Brute force(DFS), 집합, 비트마스킹

1. banned_id별로 가능한 user_id를 넣는다. (여기는 자료형 딱히 상관없을 것 같다.)

2. 배열의 크기가 8이하 => 비트마스킹 가능

3. 방문 체크한 int변수를 집합에 넣어서, 중복 검사를 한다.

 

+) 문자열 비교(banned_id & user_id)

정규표현식에 익숙하지 않아서 로직을 직접 구현했었고, 다른 코드를 보고 matches와 정규 표현식을 사용한 것을 보고 수정했다.

---

수정전

for(int i=0; i<len; i++){
    if(ban.charAt(i)=='*'){continue;}
    if(ban.charAt(i)!=user.charAt(i)){return false;}
}
return true;

---

 

 

import java.util.*;
class Solution {
    Set<Integer> bannedSet[], results;
    int setSize;
    
    public boolean correct(String user, String ban){
        int len = user.length();
        if(len != ban.length()){
            return false;
        }
        
        return user.matches(ban.replace("*", "[\\w\\d]"));
    }
    
    public void dfs(int index, int visit){
        if(index >= setSize){
            results.add(visit);
            return;
        }
        for(int num : bannedSet[index]){
            if((visit & (1<<num)) != 0){ continue;}
            dfs(index+1, visit | (1<<num));
        }
    }
    
    public int solution(String[] user_id, String[] banned_id) {
        setSize = banned_id.length;
        bannedSet = new HashSet[setSize];
        results = new HashSet<>();
        for(int i=0; i<setSize; i++){
            bannedSet[i] = new HashSet<>();//초기화
            for(int j=0; j<user_id.length; j++){
                if(correct(user_id[j], banned_id[i])){
                    bannedSet[i].add(j);
                }
            }
        }
        
        dfs(0, 0);
        return results.size();
    }
}

 

결과