[프로그래머스/Level3] 불량 사용자 (JAVA)

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• DFS

필요 자료구조
- 해당 응모 사용자 ID를 사용할지 판별 용 1차원 boolean형 배열
- 현재까지 선택된 응모한 사용자 ID의 조합 집합 Set<Set<String>> result🔥

 

 

[제재 ID 목록 만드는 메소드 dfs(선택된 응모 사용자 ID 갯수, 현재까지 선택된 사용자 ID의 집합)]

. 종료 조건 : 불량 사용자 갯수만큼 뽑았을 때, 여태 구한 제재 ID 경우를 집합에 넣는다.

. 그만큼 뽑지 않았다면, 응모한 사용자 ID 배열을 돌면서 해당 사용자 ID와 현재 탐색 중인 불량 사용자가 일치하는 경우, 해당 사용자 ID로 조합을 만든다.

for(int i = 0 ; i < user_id.length ; i++) {
    if(set.contains(user_id[i]))    continue;   // 이미 선택된 사용자 id면 pass

    if(match(user_id[i], banned_id[depth])) {
        set.add(user_id[i]);
        dfs(depth + 1, new HashSet<>(set));
        set.remove(user_id[i]);
    }
}

   ㄴ 둘이 일치하는지 확인하는 함수 : 응모한 사용자 ID와 불량 사용자 ID, 이 둘의 길이가 같고, 같은 위치에서 *이 아닌 같은 문자로 구성되어야 한다.

// 해당 사용자 ID가 현재 탐색 중인 banned_id와 일치하는지 확인하는 메소드
private static boolean match(String uId, String bId) {
    if(uId.length() != bId.length()) return false;  // 길이가 다르면 바로 pass

    for(int i = 0 ; i < uId.length() ; i++) {
        if(bId.charAt(i) != '*' && uId.charAt(i) != bId.charAt(i))
                return false;
    }

    return true;
}

 

 

 

 

🔺 코드

import java.util.*;
 
class Solution {
    static String[] user_id, banned_id;
 
    static boolean[] chk;
    static Set<Set<String>> result = new HashSet<>(); // 가능한 조합
    
    public int solution(String[] user_id, String[] banned_id) {
        this.user_id = user_id;
        this.banned_id = banned_id;
        
        chk = new boolean[banned_id.length];
        dfs(0, new HashSet<>());     
        
        return result.size(); // 가능한 조합 수
    }
    
    private static void dfs(int depth, Set<String> set) {   // set: 현재까지 선택된 사용자 ID의 집합
        if(depth == banned_id.length) {
            result.add(set);
            return;
        }
        
        for(int i = 0 ; i < user_id.length ; i++) {
            if(set.contains(user_id[i]))    continue;   // 이미 선택된 사용자 id면 pass
            
            if(match(user_id[i], banned_id[depth])) {
                set.add(user_id[i]);
                dfs(depth + 1, new HashSet<>(set));
                set.remove(user_id[i]);
            }
        }
    }
    
    // 해당 사용자 ID가 현재 탐색 중인 banned_id와 일치하는지 확인하는 메소드
    private static boolean match(String uId, String bId) {
        if(uId.length() != bId.length()) return false;  // 길이가 다르면 바로 pass
        
        for(int i = 0 ; i < uId.length() ; i++) {
            if(bId.charAt(i) != '*' && uId.charAt(i) != bId.charAt(i))
                    return false;
        }
        
        return true;
    }
}

 

---

💦 어려웠던 점

- 중복을 피한 조합을 만들어야지 생각하면서 Set을 활용할 생각은 하지 못 했다.... (Set<Set<String>> 도!)

 

 

🧐 새로 알게 된 내용

- dfs 변수에 set을 들고 다니면서 뽑은 원소 조합을 들고 다니는 아이디어

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[프로그래머스] Lv.3 불량 사용자.java