문제

[프로그래머스] 불량 사용자
https://school.programmers.co.kr/learn/courses/30/lessons/64064

풀이

조건

• * 표시에는 어떤 문자가 와도 된다.
• 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 구한다.

풀이 순서

• banned_id에 있는 목록마다 가능한 user_id의 값을 저장한다.
• DFS를 사용해 가능한 조합을 구한다.
• user_id의 값의 조합의 순서는 상관이 없으므로 중복된 경우는 제거한다.
  • HashSet을 사용한다.

코드

Java

import java.util.*;

class Solution {
    
    static boolean[] userCheck;
    static int bannedLen;
    static List<String>[] mapping;
    static List<String> userIds;
    
    static Set<List<Integer>> set;
    
    public int solution(String[] user_id, String[] banned_id) {
        bannedLen = banned_id.length; // 제제 목록 크기
        userIds = Arrays.asList(user_id); // 유저 아이디 목록
        
        // 제제 목록이 될 수 있는 유저 아이디 저장할 리스트
        mapping = new ArrayList[bannedLen];
        for(int i = 0; i < bannedLen; i++) {
            mapping[i] = new ArrayList<>();
        }
        // 제제 목록이 될 수 있는 유저 아이디 저장
        for(int i = 0; i < bannedLen; i++) {
            for(int j = 0; j < user_id.length; j++) {
                if(isMatch(user_id[j], banned_id[i])) {
                    mapping[i].add(user_id[j]);
                }
            }
        }  
        
        set = new HashSet<>();
        userCheck = new boolean[user_id.length];
        // dfs로 조합 찾기
        dfs(0);
        
        // set 크기가 정답(중복된 조합 제거됨)
        return set.size();
    }
    
    // dfs로 가능한 조합 찾는 메소드
    public void dfs(int bannedIdx) {
        // 제제 목록 수만큼 조합했다면
        if(bannedIdx == bannedLen) {
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < userCheck.length; i++) {
                if(userCheck[i]) {
                    list.add(i);
                }
            }
            // set에 넣고 종료
            set.add(list);
            return;
        }
        
        // 조합 만들기
        for(int i = 0; i < mapping[bannedIdx].size(); i++) {
            String name = mapping[bannedIdx].get(i);
            int nameIdx = userIds.indexOf(name);
            // 확인되지 않은 이름이라면 재귀 호출
            if(!userCheck[nameIdx]) {
                userCheck[nameIdx] = true;
                
                dfs(bannedIdx + 1);
                
                userCheck[nameIdx] = false;
            }
        }
    }
    
    // 가능한 이름인지 확인하는 메소드
    public boolean isMatch(String name, String target) {
        if(name.length() != target.length()) {
            return false;
        }
        for(int i = 0; i < name.length(); i++) {
            if(target.charAt(i) == '*') continue;
            
            if(name.charAt(i) != target.charAt(i)) {
                return false;
            }
        }
        
        return true;
    }
}

정리

• 중복된 조합을 처리하는 과정에서 시간이 좀 걸렸다.