불량 사용자 (프로그래머스) JAVA

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

프로그래머스

 

문제 설명

• fr*d*과 일치하는 것은 frodo, crodo
• abc1**과 일치하는 것은 abc123 
• 그러므로 조합은 frodo abc123, crodo abc123 2개입니다!!

 

문제에 대한 아이디어

배열의 크기는 1이상 8이하 입니다. banned_id도 이보다 작기때문에 완전 탐색으로 가능할 것 같습니다.

• banned_id와 일치하는 user_id를 찾습니다. 
• 각각 user_id를 모든 조합을 검사하면서 조건에 맞는 것을 찾습니다.

 

전체 코드

import java.util.*;

class Solution {
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        String[][] bans = Arrays.stream(banned_id)
            .map(banned -> banned.replace('*','.')) // 정규 표현식을 쓰기 위해 교체
            .map(banned -> Arrays.stream(user_id) // 각각의 banned_id에 맞는 user_id 구함
            .filter(id -> id.matches(banned))
            .toArray(String[]::new))
        .toArray(String[][]::new);
        Set<Set<String>> banSet = new HashSet<>();
        sol(0, bans, new HashSet<>(), banSet);
        return banSet.size();
    }
    
    public void sol(int idx, String[][] bans, Set<String> banned, Set<Set<String>> banSet){
        if(idx == bans.length){
            banSet.add(new HashSet<>(banned));
            return; 
        }
        for(String id : bans[idx]){ // 백트래킹으로 모든 조합 검사
            if(banned.contains(id)) continue;
            banned.add(id);
            sol(idx+1, bans, banned, banSet);
            banned.remove(id);
        }
    }
}