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

문제

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

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

 

접근법

응모자 아이디를 돌면서 불량 사용자의 아이디와 일치하는 경우를 찾았다.

dfs를 사용했다.

문자열을 비교하는 것은 정규표현식을 사용하였다.

중요한 포인트는 중복되는 경우들을 어떻게 처리하느냐였다.

시간이 좀 걸릴 것을 알았지만 데이터가 적었기 때문에 가능한 조합을 오름차순으로 나열해서 set에 넣었다

그러면 crodo frodo 가 되던 frodo crodo가 되던 정렬을 하게 되면 "crodo frodo"가 되기 때문에 중복 체크를 할 수 있다.

 

코드

import java.util.*;

class Solution {
    private boolean[] visited;
    private Set<String> set = new HashSet<>();
    public int solution(String[] user_id, String[] banned_id) {

        visited = new boolean[user_id.length];
        dfs(0, "", user_id, banned_id);

        return set.size();
    }

    private void dfs(int n, String str, String[] user_id, String[] banned_id) {
        if(n == banned_id.length){
            String[] strArr = str.split(" ");

            Arrays.sort(strArr);
            StringBuilder sb = new StringBuilder();
            for(String s : strArr){
                sb.append(s);
            }
            set.add(sb.toString());
            return;
        }
        String reg = banned_id[n].replace("*", "[\\w\\d]");

        for(int i=0;i< user_id.length;i++){
            if(user_id[i].matches(reg) && !visited[i]){
                visited[i] =true;
                dfs(n+1, str+ " " +user_id[i], user_id, banned_id);
                visited[i] = false;
            }
        }

    }
}