[프로그래머스] 2019 카카오 겨울인턴. 불량 사용자 (Java)

Problem

• 문제 링크

사용자 목록 user_id 와 불량 사용자 목록 banned_id 가 주어졌을 때 당첨에서 제외되어야 하는 사용자 목록의 경우의 수를 구하는 문제입니다.

Solution

최대 길이가 8 이기 때문에 완전 탐색을 해도 괜찮습니다.

사용자 목록에서 DFS 로 banned_id.length 만큼의 사용자를 뽑습니다.

뽑힌 사용자들을 banned_id 와 비교하여 일치하는 케이스를 구하면 됩니다.

중복된 값은 모두 하나의 경우가 되기 때문에 set 에 넣어서 필터링 해줍니다.

boolean isSameString(String a, String b) 함수는 두 String 의 일치 여부를 판단합니다.

boolean isBannedUsers(Set<String> set, String[] banned_id) 함수는 뽑힌 set 과 banned_id 목록을 비교하여 경우의 수에 해당되는지 판단합니다.

어차피 중복은 제거되기 때문에 banned_id 와 일대일 비교를 하기 위해 set 을 LinkedHashSet 으로 선언했습니다.

Java Code

import java.util.*;

class Solution {
    private Set<Set<String>> result;
    
    public int solution(String[] user_id, String[] banned_id) {
        result = new HashSet<>();
        dfs(user_id, banned_id, new LinkedHashSet<>());
        return result.size();
    }
    
    private void dfs(String[] user_id, String[] banned_id, Set<String> set) {
        if (set.size() == banned_id.length) {
            if (isBannedUsers(set, banned_id)) {
                result.add(new HashSet<>(set));
            }
            
            return;
        }
        
        for (String userId : user_id) {
            if (!set.contains(userId)) {
                set.add(userId);
                dfs(user_id, banned_id, set);
                set.remove(userId);
            }
        }
    }
    
    private boolean isBannedUsers(Set<String> set, String[] banned_id) {
        int i = 0;
        
        for (String user : set) {
            if (!isSameString(user, banned_id[i++])) {
                return false;
            }
        }
        
        return true;
    }
    
    private boolean isSameString(String a, String b) {
        if (a.length() != b.length()) {
            return false;
        }
        
        for (int i = 0; i < a.length(); i++) {
            if (b.charAt(i) == '*') continue;
            
            if (a.charAt(i) != b.charAt(i)) {
                return false;
            }
        }
        
        return true;
    }
}