Today I Learned

간만에 프로그래머스에서 코테 문제를 풀었다.

불량사용자

프로그래머스64064 https://school.programmers.co.kr/learn/courses/30/lessons/64064

문제

사용자 아이디 목록 user_id (알파벳 소문자와 숫자로 구성, 길이 1~8)
제재 아이디 목록 banned_id (알파벳 소문자, 숫자, '*' 포함, 길이 1~8)가 주어진다.
banned_id에서 '*' 문자는 와일드카드 용도로 임의의 문자 하나를 대체할 수 있다.
제재 아이디 목록에 매핑될 수 있는 사용자 아이디의 모든 가능한 조합을 찾아서, 그 조합의 수를 반환하는 함수를 만들어라.

문제 풀이

1. 우선 매핑 가능성을 검사하는 메서드 isMatch를 만든다. 여기선 userId가 bannedId에 매핑될 수 있는지를 검사한다. 두 문자열의 길이가 같아야되고, 각 문자를 비교하여 bannedId의 문자와 다르고 '*'가 아닐 경우 false를 반환해, 모든 문자가 매칭되면 true를 반환한다.

2. 백트래킹을 이용해서 가능한 매핑 조합을 찾는 메서드 findComb를 만든다. index가 possible 리스트의 크기와 같아지면 지금 조합을 result에 넣는다. 각 index에서 가능한 유저 아이디를 선택해 중복되지 않는 경우에만 추가한다. 재귀적으로 작동해서 다음 인덱스로 넘어가며 선택한 아이디를 다시 제거해서 백트래킹을 수행한다.

3. solution 메서드에서 위의 두 메서드를 활용해서 문제를 해결한다. banned_id 리스트의 각 아이디에 대해서 user_id 리스트를 순회하면서 매핑 가능한 아이디를 match 리스트에 추가한다.
   각 match 리스트를 possible 리스트에 추가하고, findComb 메서드를 이용해서 가능한 모든 조합을 result에 넣는다. 마지막으로 result의 크기를 반환하면 완료!

Java 코드

import java.util.*;

class Solution {
    private static boolean isMatch(String userId, String bannedId) {
        if(userId.length() != bannedId.length()) return false;
        
        for(int i=0; i<userId.length(); i++){
            if(bannedId.charAt(i) != '*' && userId.charAt(i) != bannedId.charAt(i)) return false;
        }
        return true;
    }
    
    private static void findComb(List<List<String>> possible, int index, Set<String> current, Set<Set<String>> result){
        if(index == possible.size()){
            result.add(new HashSet<>(current));
            return;
        }
        for(String user : possible.get(index)){
            if(!current.contains(user)){
                current.add(user);
                findComb(possible, index+1, current, result);
                current.remove(user);
            }
        }
    }
    
    
    public int solution(String[] user_id, String[] banned_id) {
        List<List<String>> possible = new ArrayList<>();
        
        for(String banned : banned_id){
            List<String> match = new ArrayList<>();
            
            for (String user : user_id){
                if(isMatch(user, banned)) match.add(user);
            }
            possible.add(match);
        }
        
        Set<Set<String>> result = new HashSet<>();
        findComb(possible, 0, new HashSet<>(), result);
    
        return result.size();
    }
}