프로그래머스 - 불량 사용자 문제 (자바)

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

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

dfs를 통해서 가능한 모든 경우(모든 순서, 모든 유저)를 구하고 가능한 벤 목록인지 체크합니다. 

이후 ArrayList를 set으로 바꾸면서 저장하는데

이유는 ArrayList는 유효한 순서를 가지기 때문에 동일한 값들을 가지더라도 순서가 다르면 다르게 판단합니다. 때문에 resultSet에 ArrayList를 그대로 넣으면 순서만 다른 경우 다르다고 판단하게 됩니다.

이 때문에 순서를 보장하지않은 다르게 말하면 순서는 같고 다름을 판단하는데 의미없는 set을 사용하여 해결하였습니다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

// 프로그래머스 불량 사용자 문제
class Solution {
    private Set<Set<String>> resultSet;
    public int solution(String[] user_id, String[] banned_id) {
        resultSet = new HashSet<>();
        dfs(user_id, banned_id, new ArrayList<>());
        return resultSet.size();
    }

    public void dfs(String[] user_id, String[] banned_id, ArrayList<String> banner_list) {
        if (banner_list.size() == banned_id.length) {
            if(isPossibleBannedUsers(banner_list, banned_id)) {
                resultSet.add(new HashSet<>(banner_list));
            }
            return;
        }

        for (int i = 0; i < user_id.length; i++) {
            if(!banner_list.contains(user_id[i])) {
                banner_list.add(user_id[i]);
                dfs(user_id, banned_id, banner_list);
                banner_list.remove(user_id[i]);
            }
        }
    }

    public boolean isPossibleBannedUsers(ArrayList<String> banner_list, String[] banner_id) {
        for(int i = 0; i < banner_list.size(); i++) {
            if(!isCorrectStringPattern(banner_list.get(i), banner_id[i])) {
                return false;
            }
        }
        return true;
    }

    public boolean isCorrectStringPattern(String user_id, String pattern) {
        if (user_id.length() != pattern.length()) return false;

        for (int i = 0; i < user_id.length(); i++) {
            if(pattern.charAt(i) == '*') continue;

            if (user_id.charAt(i) != pattern.charAt(i)) return false;
        }
        return true;
    }
}