프로그래머스 - 불량 사용자 - DFS - Java

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/64064

2. 풀이

✨ 핵심 Point = Stream과 HashSet

1. Stream 사용하기.

String[][] bans = Arrays.stream(banned_id)
						.map(banned -> banned.replace("*", "."))
						.map(banned -> Arrays.stream(user_id)
											.filter(id -> id.matches(banned))
											.toArray(String[]::new))
						.toArray(String[][]::new);

2. HashSet사용하여 중복 값 제거하여 넣기.

2-1. main에서 넣어줄때 new HashSet<>()으로 새로 생성해서 넣어준다.

Set<Set<String>> banComb = new HashSet<>();
dfs(0, bans, new HashSet<>(), banComb);
System.out.println(banComb.size());

2-2. dfs함수에서 중요한건 if문에서 탈출할 때 반드시
banComb.add(new HashSet<>(banSet));

public static void dfs(int index, String[][] bans, Set<String> banSet, Set<Set<String>> banComb) {
	
	if(index == bans.length) {
		//banComb.add(banSet); // ❌
		banComb.add(new HashSet<>(banSet));
		return;
	}
	
	for(String id : bans[index]) {
		if(!banSet.contains(id)) {
			banSet.add(id);
			dfs(index+1, bans, banSet, banComb);
			banSet.remove(id);
		}
	}
}

3. 전체 코드

import java.util.*;
import java.util.stream.*;

class Solution {
    public int solution(String[] user_id, String[] banned_id) {
        
        String bans[][] = Arrays.stream(banned_id)
                            .map(banned -> banned.replace("*", "."))
                            .map(banned -> Arrays.stream(user_id)
                                            .filter(id -> id.matches(banned))
                                            .toArray(String[]::new))
                            .toArray(String[][]::new);
        HashSet<HashSet<String>> banComb = new HashSet<>();
        dfs(0, bans, new HashSet<String>(), banComb);
        return banComb.size();
    }
    
    public void dfs(int index, String[][]bans, HashSet<String> banSet, HashSet<HashSet<String>>banComb){
        if(index == bans.length){
            banComb.add(new HashSet<>(banSet));
            return;
        }
        
        for(String id : bans[index]){
            if(!banSet.contains(id)){
                banSet.add(id);
                dfs(index+1, bans, banSet, banComb);
                banSet.remove(id);
            }
        }
    }
}