[level 3] 불량 사용자 - 64064

문제 요약

주어진 사용자 아이디 목록과 불량 사용자 아이디 목록에서, 불량 사용자 아이디 목록에 매핑되는 사용자 아이디 목록을 찾아내서 당첨에서 제외되어야 할 제재 아이디 목록의 경우의 수를 구하는 문제입니다. 각 사용자 아이디는 알파벳 소문자와 숫자로 이루어진 문자열입니다. 불량 사용자 아이디 목록은 각 아이디마다 문자열 내에서 일부 문자를 '*'로 가려서 주어집니다.

---

문제 분석

불량 사용자 아이디 목록에서 가능한 조합 구하기

각 불량 사용자 아이디에 대해 가능한 모든 사용자 아이디 조합 구하기

중복 제외한 가능한 경우의 수 구하기

DFS를 사용하자.

---

코드

import java.util.*;
class Solution {
    static Set<Set<String>> resultSet;
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        // 제재 아이디 목록을 담을 set생성
        resultSet = new HashSet<>();
        // 제재 아이디들을 각각의 banned_id에 맞게 저장해줄 list생성
        List<List<String>> list = new ArrayList<>();
        // banned_id를 기반으로 순회
        for(int b = 0; b < banned_id.length; b++){
            List<String> innerList = new ArrayList<>();
            for(int u = 0; u < user_id.length; u++){
                if(isMatch(user_id[u], banned_id[b])){
                    innerList.add(user_id[u]);
                }
            }
            list.add(innerList);
        }
        // 위에서 찾은 list를 기반으로 set에 제재 아이디 목록들을 만들어줌
        find(list, 0, new HashSet<String>());
        return resultSet.size();
    }
    public void find(List<List<String>> list, int cnt, Set<String> idSet){
        // cnt는 banned_id의 개수와 일치해야 종료할 수 있다.
        if(cnt == list.size()){
            // 그리고 지금 찾은 제재 아이디 목록개수 또한 일치해야지만 set을 저장할 수 있다.
            if(idSet.size() == list.size()){
                resultSet.add(new HashSet<>(idSet));
            }
            return;
        }
        // 반복문을 통해 cnt번쨰 불량사용자에 해당하는 아이디들을 set에 저장한다.
        for(String id : list.get(cnt)){
            if(idSet.contains(id) == false){
                idSet.add(id);
                find(list, cnt+1, idSet);
                idSet.remove(id);
            }
        }
    }
    public boolean isMatch(String userId, String bannedId){
        boolean check = true;
        // 자리수 확인
        if(userId.length() != bannedId.length()){
            return false;
        }
        // 돌아가며 확인
        for(int i = 0; i < userId.length(); i++){
            if(userId.charAt(i) != bannedId.charAt(i) && bannedId.charAt(i) != '*'){
                check = false;
                break;
            }
        }
        return check;
    }
}

---

정리

새로 배운 내용

없음

개선할 점

문제 로직을 생각하는데 시간이 좀 걸렸다. 알고 보면 쉬운 문젠데 왜 그랬는지 지금도 모르겠다.

더 찾아볼만한 사항

 

---