[프로그래머스 풀이] 불량 사용자

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

문제의 목적은 주어진 응모자 아이디 리스트와 불량사용자 아이디 리스트를 이용하여 제제 아이디 목록을 몇개나 만들 수 있는가 였다.

이를 구하기 위해, 전체적인 순서는 다음과 같다.

1. 각각의 불량 사용자와 응모자들을 비교하여 불량 사용자 마다의 응모자 집합을 만든다.
   ( -> 만들어지는 제제 아이디 목록이 이전에 존재했었는지를 O(1)로 확인하기 위해 HashSet을 사용하였다. )
2. 만들어진 집합들을 통해 에 대해 BruteForce ( 완전 탐색 )을 이용하여 만들어 질 수 있는 제제 아이디 리스트를 만들어 이미 만들어진 것인지 확인한다. 

디테일은 주석을 통해 작성하였다. 

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

class Solution {
    public static int answer = 0;   // 답
    public static HashSet<HashSet> answerSet = new HashSet<>(); // 만들어진 제제 아이디 목록이 이미 존재했었는지를 확인하기 위해 이전에 만들어진 집합을 저장한다.
    public int solution(String[] user_id, String[] banned_id) {
        ArrayList<HashSet> list = new ArrayList<>(); // 각각의 banned_id에 대해 만족할 수 있는 응모자를 저장하기 위한 HashSet이다.

        // 아래 2중 반복문을 통해 user_id와 banned_id를 비교하여 set을 생성하고, 이를 리스트에 추가한다.
        for (String banned : banned_id){
            HashSet<String> set = new HashSet<>();
            for (String user : user_id){
                if (checker(banned, user))
                    set.add(user);
            }
            list.add(set);
        }

        // run_brute() 함수 내에서 아래 HashSet의 용도를 설명한다.
        HashSet<String> answerSet = new HashSet<>();

        //
        run_Brute(0, list, answerSet);
        return answer;
    }

    // 아래 함수를 통해 만들어질 수 있는 모든 제제목록을 생성한다.
    //      1. depth 를 통해 각각의 banned_id에 가능한 응모자들을 탐색한다.
    //      2. answerSet를 통해 1번에서 추가되는 응모자가 이미 제제목록에 존재하는지를 확인한다.
    public void run_Brute (int depth, ArrayList<HashSet> list, HashSet<String> answerSet) {

        //  아래 조건문은 모든 밴 목록에 대하여 수행한 경우에 실행된다.
        //      만들어진 answerSet이 이미 존재 했었는지를 확인한다. 존재 하지 않았다면 전역변수로 선언된 answerSet에 해당 answerSet를 추가한다.
        if (depth == list.size()){
            for (HashSet<String> temp_set : this.answerSet)
                if (temp_set.containsAll(answerSet))
                    return;
            // 지역변수 answerSet은 하나의 객체 이므로 새로이 객체를 만들어 전역변수 answerSet에 추가한다. 
            HashSet<String> set = new HashSet<>();
            for (String temp : answerSet) set.add(temp);
            this.answerSet.add(set);
            answer ++;
            return;
        }
        // 특정 밴 문자열의 집합 가져오기
        HashSet<String> set = list.get(depth);
        for (String curr : set){
            if (!answerSet.contains(curr)){
                answerSet.add(curr);    // 정답 집합에 해당 String을 추가한다.
                run_Brute(depth+1, list, answerSet); // 리스트 내의 각각의 밴 아이디에 대해 수행하기 위해 재귀적으로 수행한다.
                answerSet.remove(curr); // 수행후 정답 집합에서 해당 String 을 제거한다. 
            }
        }
    }

    // 주어진 문자열과 밴문자열을 비교하여
    //  1. 문자열 길이가 다른경우 리턴 false
    //  2. 동일 인덱스의 문자가 다를 때 밴문자열의 문자가 *이 아닌경우 리턴 false
    public boolean checker(String starString, String s){
        if ( starString.length() != s.length() ) return false;
        else {
            for (int i=0; i< starString.length(); i++){
                if (starString.charAt(i) != s.charAt(i) && starString.charAt(i) != '*')
                    return false;
            }
            return true;
        }
    }
}