불량 사용자 (자료구조의 앝은 복사 vs 깊은 복사)

사용 알고리즘: dfs, 자료구조-세트

사용 언어: java

 

import java.util.*;

class Solution {
    Set<Set<String>> answer = new HashSet<>();
    
    public int solution(String[] user_id, String[] banned_id) {
        Set<String> set = new HashSet<>();
        dfs(user_id, banned_id, set, 0);
        
        return answer.size();
    }
    
    public void dfs(String[] user_id, String[] banned_id, Set<String> set, int bDept) {
        if(bDept == banned_id.length) {
            //answer.add(set);
            answer.add(new HashSet<>(set));
            return;
        }
        
        for(String ui : user_id) {
            if(set.contains(ui)) continue;
            if(ui.length() != banned_id[bDept].length()) continue;
            
            boolean match = true;
            for(int i=0; i<ui.length(); i++) {
                if(banned_id[bDept].charAt(i) != '*' && ui.charAt(i) != banned_id[bDept].charAt(i)) {
                    match = false;
                    break;
                }
            }
            
            if(match) {
                set.add(ui);
                dfs(user_id, banned_id, set, bDept+1);
                set.remove(ui);
            }
        }
    }
}

 

아~~~니

answer.add(set); 은 틀리고

answer.add(new HashSet<>(set)); 은 맞음..

 

1. answer.add(set) -> 얕은 복사st

• set은 dfs 함수 내에서 계속해서 변경되는 Set 객체입니다.
• answer.add(set)은 set 객체 자체의 참조를 answer 리스트에 추가합니다.
• 따라서 dfs 함수가 종료된 후 answer 리스트의 모든 요소는 동일한 set 객체를 가리키게 됩니다.
• set이 dfs 함수 내에서 변경됨에 따라 answer 리스트의 모든 요소도 함께 변경됩니다.
• 결과적으로 answer 리스트에는 마지막에 dfs 함수에서 사용된 set의 최종 상태만 저장됩니다.

2. answer.add(new HashSet<>(set)) -> 깊은 복사st

• new HashSet<>(set)은 set 객체를 복사하여 새로운 HashSet 객체를 생성합니다.
• answer.add(new HashSet<>(set))은 복사된 새로운 HashSet 객체의 참조를 answer 리스트에 추가합니다.
• 따라서 dfs 함수가 종료된 후 answer 리스트의 각 요소는 서로 다른 HashSet 객체를 가리키게 됩니다.
• 각 HashSet 객체는 dfs 함수가 특정 깊이(bDept)에 도달했을 때의 set의 상태를 복사하여 저장하므로, 각기 다른 조합을 나타냅니다.