[2019 카카오 인턴십]불량 사용자★

📍 문제 설명

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

프로그래머스

 

💡 접근

범위가 좁다보니까 모든 user_id를 banned_id 만큼 생성해서 맞는지 확인하려고 했었는데, 순열로 풀자니 중복 문제가 조합으로 풀자니 banned_id에서 매칭되는 순서 문제가 발생했다.

 

그래서 타 블로그를 참고 했다.

먼저 banned_id를 기준을 넣을 수 있는 user_id를 보관해두는 list를 만들었다.

(정규표현식을 이용했고 '.'라는 문자는 임의의 한 문자를 의미하는 것을 이용하여 넣어주었음)

user_id가 frodo, fradi, abc123이 있고 banned_id가 fr*d*, abc1** 있다면 [[frodo, fradi], [abc123] 이런식으로 저장하는 방식이었다.

그리고 나서 hashSet을 사용하는 재귀를 사용했는데 depth를 이용해서 리스트에 담긴 아이디들을 모두 담을 수 있도록 하였고 banned_id와 중복매칭의 가능성도 있으니 set에 담겨있는 유저는 넣지 않도록 하였다.

 

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.regex.Pattern;

class Main {
    static HashSet<HashSet<String>> result;
    static ArrayList<ArrayList<String>> bannedUserList;

    public int solution(String[] user_id, String[] banned_id) {
        result = new HashSet<HashSet<String>>();
        bannedUserList = new ArrayList<ArrayList<String>>();

        for (String bannedId : banned_id) {
            //n번째 인덱스에 들어갈 수 있는 제재 아이디들 모두 구하기
            String pattern = bannedId.replace('*', '.');
            ArrayList<String> valueList = new ArrayList<>();
            for (String userId : user_id) {
                boolean isMatch = Pattern.matches(pattern, userId);
                if (isMatch) valueList.add(userId);
            }
            bannedUserList.add(valueList);
        }
        dfs(new HashSet<String>(), 0);
        return result.size();
    }

    void dfs(HashSet<String> add, int depth) {
        if (depth == bannedUserList.size()) {
            result.add(new HashSet<>(add));
            return;
        }
        else {
            // depth번째에 들어갈 수 있는 아이디 목록에서 뽑음
            for (String userId : bannedUserList.get(depth)) {
                // 이미 목록에 들어가있으면 담지 않음
                if (!add.contains(userId)) {
                    add.add(userId);
                    dfs(add, depth + 1);
                    add.remove(userId);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Main main = new Main();

        String[] user_id = {"frodo", "fradi", "crodo", "abc123", "frodoc"};
        String[] banned_id = {"fr*d*", "abc1**"};
        main.solution(user_id, banned_id);
    }
}