[JAVA] 프로그래머스 LEVEL3 불량 사용자

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

프로그래머스

코딩테스트 연습 > 2019 카카오 개발자 겨울 인턴십 > 불량 사용자

 

난이도: LEVEL3

알고리즘 유형: 백트래킹(완탐) 

 

문제 접근

이번 문제는 정상 아이디와 불량 아이디가 주어지고 

정상 아이디의 경우의 수를 찾는 문제이다. 

 

문제 조건 

모든 불량 아이디에는 '*'이 1개 이상 포함된다. 

정상 아이디는 중복이 없다. 

나열된 순서와 상관없이 아이디 목록이 동일하다면 같은 것으로 처리한다. 

 

1. 해당 user_id에 조건이 맞는 banned_id (1: N) 구하기

 

ex)

user_id = aaa

가능한 불량 id = ***, a**, aa*, a*a .... 

 

해당 user_id에 조건이 맞는 불량 id를 Set<String>으로 넣어준다.

ArrayList로 저장보다 Set contains 메소드는 더 빠르기 때문에 Set 자료구조 활용 

 

길이가 다르면 일단 해당 불량 id는 탈락이다. → 바로 continue 

길이가 같다면 전체 비교를 한다. 

만약 서로 다른 단어가 들어가 있는데 불량 id가 '*"가 아니라면 해당 불가능한 케이스여서 break

static ArrayList<Set<String>> list = new ArrayList<>();

for(String cur : user_id){
    Set<String> set = new HashSet<>();
    int cur_length = cur.length();
    for(String next : banned_id){
        // 길이가 다르면 pass
        if(next.length() != cur_length) continue;
        boolean flag = true;
        for(int i = 0; i < cur_length; i++){ // 검사 시작 
            if(next.charAt(i) == '*') continue;
            if(next.charAt(i) != cur.charAt(i)){
                flag = false;
                break;
            }
        }
        if(flag) set.add(next);
    }
    list.add(set);
}

 

2. 미리 구한 user_id의 후보들을 활용해서 완전탐색

 

완탐의 결과물에서 answer 뽑는 기준 

모든 불량 id를 사용해야 한다.  모든 불량 id는 user_id에 포함되기 때문이다.

순서가 다르고 내용이 같은 건 1개의 경우의 수로 취급 

 

완전탐색할 때 이번 user_id를 선택 안하는 케이스가 존재할 수 있다. 

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

find(0, new ArrayList<>());

public static void find(int depth, ArrayList<Integer> check){
    if(depth == user.length){
        boolean flag = true;
        for(int i = 0; i < banned.length; i++){
            if(!visited[i]){
                flag = false;
                break;
            }
        }
        if(flag){
            StringBuilder sb = new StringBuilder();
            for(int next : check){
                sb.append(next);
            }
            String result = sb.toString();
            if(!set.contains(result)){
                set.add(result);
                answer++;
            }
        }
        return;
    }
    for(int i = 0; i < banned.length; i++){
        if(visited[i]) continue;
        if(list.get(depth).contains(banned[i])){
            visited[i] = true;
            ArrayList<Integer> temp = new ArrayList<>(check);
            temp.add(depth);
            find(depth + 1, temp);
            visited[i] = false;
        }
    }
    find(depth + 1, new ArrayList<>(check));
}

정답 코드 

import java.util.*;
class Solution {
    static ArrayList<Set<String>> list = new ArrayList<>();
    static String [] user; 
    static String [] banned;
    static int answer = 0;
    static boolean [] visited;
    static HashSet<String> set = new HashSet<>();
    public int solution(String[] user_id, String[] banned_id) {
        user   = user_id;
        banned = banned_id;
        visited = new boolean [banned_id.length];
        for(String cur : user_id){
            Set<String> set = new HashSet<>();
            int cur_length = cur.length();
            for(String next : banned_id){
                // 길이가 다르면 pass
                if(next.length() != cur_length) continue;
                boolean flag = true;
                for(int i = 0; i < cur_length; i++){ // 검사 시작 
                    if(next.charAt(i) == '*') continue;
                    if(next.charAt(i) != cur.charAt(i)){
                        flag = false;
                        break;
                    }
                }
                if(flag) set.add(next);
            }
            list.add(set);
        }  
        find(0, new ArrayList<>());
        return answer;
    }
    public static void find(int depth, ArrayList<Integer> check){
        if(depth == user.length){
            boolean flag = true;
            for(int i = 0; i < banned.length; i++){
                if(!visited[i]){
                    flag = false;
                    break;
                }
            }
            if(flag){
                StringBuilder sb = new StringBuilder();
                for(int next : check){
                    sb.append(next);
                }
                String result = sb.toString();
                if(!set.contains(result)){
                    set.add(result);
                    answer++;
                }
            }
            return;
        }
        for(int i = 0; i < banned.length; i++){
            if(visited[i]) continue;
            if(list.get(depth).contains(banned[i])){
                visited[i] = true;
                ArrayList<Integer> temp = new ArrayList<>(check);
                temp.add(depth);
                find(depth + 1, temp);
                visited[i] = false;
            }
        }
        find(depth + 1, new ArrayList<>(check));
    }
}