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

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

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

import java.util.*;

class Solution {
    static Set<String> set=new HashSet<>();
    static ArrayList<ArrayList<String>> li=new ArrayList<>();
    public int solution(String[] user_id, String[] banned_id) {
        for (int i=0; i<banned_id.length; i++){
            li.add(new ArrayList<>());
            findString(i, user_id, banned_id[i]);
        }
        dfs(0, banned_id.length, new String[banned_id.length]);
        return set.size();
    }
    public void dfs(int num, int size, String[] arr){
        if (num==size){
            String[] temp=Arrays.copyOf(arr, size);
            Arrays.sort(temp);
            StringBuilder sb=new StringBuilder("");
            for (String s: temp){
                sb.append(s);
            }
            set.add(sb.toString());
            return;
        }
        for (int i=0; i<li.get(num).size(); i++){
            String s=li.get(num).get(i);
            boolean flag=false;
            for (int j=0; j<num; j++){
                if (s.equals(arr[j])){
                    flag=true;
                    break;
                }
            }
            if (flag) continue;
            arr[num]=s;
            dfs(num+1, size, arr);
        }
    }
    
    public void findString(int num, String[] user_id, String ban){
        for (String uid : user_id){
            if (uid.length()==ban.length()){
                boolean flag=true;
                for (int i=0; i<uid.length(); i++){
                    if (ban.charAt(i)!='*' && ban.charAt(i)!=uid.charAt(i)){
                        flag=false;
                        break;
                    }
                }
                if (flag){
                    li.get(num).add(uid);
                }
            }
        }
    }
}

정규표현식을 이용했더라면 더 간단했을.. 백트래킹 문제.

 

findString()에서 각 banned_id와 일치하는 후보군들을 모두 저장해준다.

이후 dfs()에서 그 후보군의 가능한 경우를 뽑은 뒤, 중복되는 거 제외(이전까지 for 문 돌려서..) 한 후, 뽑은 문자열들을 정렬해서 set에 넣어주는 형태로 했다.

 

하지만 다른 분들의 코드를 보니, 더 간단하게 풀 수 있다. (https://moonsbeen.tistory.com/45)

 

 regex[i] = banned_id[i].replace("*", "."); 로 정규표현식 형태로 바꿔준 뒤,

banned_id 마다, user_id를 쫙 돌면서 일치하고(이때 matches를 써준다), 미방문인(중복을 피하기 위해) 것들을 string에 넣어주고, 최종적으로 중복되는 것을 피하기 위해 set에 넣는다.