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

코드 힌트

1. DFS(깊이 우선 탐색) 활용
   • 이 문제는 모든 가능한 경우의 수를 찾는 문제로, DFS가 적절한 해결 방법입니다.
   • 매칭이 성공한 경우 백트래킹(backtracking)을 통해 다음 가능한 조합을 계속 탐색합니다.
2. 와일드카드 문자(*) 처리
   • banned_id에 포함된 * 문자는 모든 문자와 매칭되므로, 이 점을 유의하며 처리합니다.
3. 고유한 조합 저장
   • 조합이 동일한 아이디들을 포함하더라도 순서가 다르면 같은 조합으로 간주됩니다.
     따라서 Set<Set<String>>을 사용해 고유한 조합을 저장합니다.
   • new HashSet<>(currentSet)을 통해 조합을 복사하여 uniqueSet에 추가합니다.
   • new HashSet<>(set)을 사용해 새로운 Set 객체를 생성하여 추가하는 이유는, 기존 Set의 참조를 복사하는 것이 아니라 값 자체를 복사하기 위해서입니다.
4. 백트래킹을 통한 조합 탐색
   • 하나의 아이디가 사용된 후 다음 아이디를 탐색할 때는 백트래킹을 사용해 다시 이전 상태로 되돌립니다.
     이를 통해 모든 가능한 조합을 탐색할 수 있습니다.

 

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    
    // 전역 변수: 사용자 아이디와 제재 아이디 배열
    String[] userId;
    String[] bannedId;
    // 고유한 아이디 조합을 저장할 Set
    Set<Set<String>> uniqueSet = new HashSet<>();
    
    // 메인 solution 함수: 제재 아이디에 매칭될 수 있는 고유한 경우의 수를 찾음
    public int solution(String[] user_id, String[] banned_id) {
        
        userId = user_id; // 사용자 아이디 배열 초기화
        bannedId = banned_id; // 제재 아이디 배열 초기화
        
        // 방문 여부를 체크할 배열 생성
        boolean[] visit = new boolean[userId.length];
        
        // DFS를 이용해 모든 가능한 조합 탐색
        dfs(visit, 0, new HashSet<>());
        
        // 고유한 조합의 수 반환
        return uniqueSet.size();
    }
    
    // DFS로 모든 조합을 탐색하는 함수
    public void dfs(boolean[] visit, int idx, Set<String> currentSet) {
        // 제재 아이디의 모든 조건을 만족하는 경우
        if (idx == bannedId.length) {
            uniqueSet.add(new HashSet<>(currentSet)); // 조합을 고유 Set에 저장
            return;
        }
        
        // 사용자 아이디를 하나씩 검사
        for (int i = 0; i < userId.length; i++) {
            // 아직 방문하지 않았고, 현재 제재 아이디와 매칭되는 경우
            if (!visit[i] && checkId(userId[i], bannedId[idx])) {
                visit[i] = true; // 방문 처리
                currentSet.add(userId[i]); // 현재 아이디를 조합에 추가
                
                // 다음 제재 아이디로 넘어감
                dfs(visit, idx + 1, currentSet);
                
                // 백트래킹: 방문 취소 및 아이디 제거
                visit[i] = false;
                currentSet.remove(userId[i]);
            }
        }
    }
    
    // 사용자 아이디와 제재 아이디가 매칭되는지 검사하는 함수
    public boolean checkId(String id, String compareId) {
        // 길이가 다르면 매칭되지 않음
        if (id.length() != compareId.length()) return false;
        
        // 각 문자를 비교하여 매칭 여부 확인
        for (int i = 0; i < id.length(); i++) {
            // compareId의 문자가 '*'이 아니고 두 문자가 다르면 매칭 실패
            if (compareId.charAt(i) != '*' && id.charAt(i) != compareId.charAt(i)) 
                return false;
        }
        return true; // 모든 조건을 만족하면 매칭 성공
    }
}