[코테] 프로그래머스 불량 사용자 64064: DFS JAVA

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

프로그래머스

 

 

class Solution {
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        return answer;
    }
}

응모자 아이디, 제재 아이디가 들어온다.

제재 아이디는 중간중간 *로 처리가 되어있다.

당첨에서 제외되어야 할 제재 아이디 목록은 몇 가지 경우의 수가 가능한지 응답한다.

 

풀이

경우의 수에 따른 id를 저장하는 Set을 만든다.

Set<String> set = new HashSet<>();

 

경우의 수를 저장하는 Set 목록을 만든다.

Set<Set<String>> answer = new HashSet<>();

import java.util.*;

public class Solution {
    String[] user_id;
    String[] banned_id;

    public int solution(String[] user_id, String[] banned_id) {
        this.user_id = user_id;
        this.banned_id = banned_id;
        Set<String> bannedCase = new HashSet<>();

        Set<Set<String>> caseList = new HashSet<>();

        dfs(caseList, bannedCase, 0);

        return caseList.size();
    }

    public void dfs(Set<Set<String>> caseList, Set<String> bannedCase, int depth) {
        // 불량 사용자 탐색이 끝나면 하나의 경우의 수 완성
        if(depth == banned_id.length) {
            caseList.add(new HashSet<>(bannedCase));
            return;
        }

        // 사용자 아이디로 루프
        for(int i = 0 ; i < user_id.length ; i++) {
            if(bannedCheck(i, depth, bannedCase)){
                bannedCase.add(user_id[i]);

                dfs(caseList, bannedCase, depth+1);

                bannedCase.remove(user_id[i]); // 백트래킹
            }
        }
    }

    public boolean bannedCheck(int i, int depth, Set<String> answer) {
        return user_id[i].matches(banned_id[depth].replace("*",".")) && !answer.contains(user_id[i]);
    }
}

 

✅ set.add(new HasSet<>(answer)); 하는 이유

=> 주소를 참조하는데 answer값은 계속 변화함.

 

✅ bannedCheck 설명

user_id[i].matches(banned_id[depth].replace("*","."))

=> 현재 유저가 banned_id에 해당하는지 검사. 이미 answer에 들어가있는 id면 false.

 

✅ 백트래킹 부분 설명

dfs를 빠져나오면서 bannedCase에 저장되어있는 아이디를 삭제. 

 

총 정리

사용자 아이디로 for문을 돌림. 만약 banned_id와 매치된다면 bannedCase에 추가.

dfs 다시 진입. depth+1.

depth가 banned id 길이와 동일해지면 하나의 경우의 수 완성. return. (여기서 뎁스는 banned id에 일치하는 아이디 갯수와 동일함.)

빠져나오면 직전 userId bannedCase에서 삭제.

삭제한 채로 그 다음 user_id 탐색. 만약 banned id 존재한다면 하나의 경우의 수 또 완성. return.

빠져나오면 직전 userId bannedCase에서 삭제.

삭제한 채로 그 다음 user_id 탐색. 만약 if문 만족하는 값이 없으면 for문 끝. dfs 함수 하나 종료. 

그 다음 answer.remove 실행. 

반복.