[알고리즘] 프로그래머스 불량 사용자 :: 우유

 

| 프로그래머스 불량 사용자

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

프로그래머스

코드 설명

불량사용자의 조합이 여러가지 나올 수 있기 때문에 중복을 허용하지 않는 set 을 사용하여 불량사용자 조건에 해당되는 user들을 set에 모두 중복, 순서에 상관없이 add 해주는 방법으로 문제를 구현하였다.

유저 아이디(str1)가 불량사용자의 아이디(str2)에 해당이 되는지 검증하여 true/false 로 나타내는 함수이다.
첫번째 if문에서는 길이를 비교하여 길이가 맞지 않으면 false를 return 해주었고, 그아래 코드에선
각 문자를 비교하여 * 이 아니거나 문자열이 일치하지 않는 경우 false를 return 해주었다.

    public boolean check(String str1, String str2) {
        boolean flag = true;

        if (str1.length() != str2.length()) {
            flag = false;
            return flag;
        }

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

        return flag;
    }

여기서 백트래킹 방법으로 HashSet에 다가 해당 되는 userId를 계속 add 해주었다.
유저 수 만큼 for문을 돌려서 해당 유저가 불량 사용자 조건에 해당 되는지를 체크하여 해당된다고 하면 set에 add를 해주었다.

여기서 헷갈렸던 포인트는 
DFS(new HashSet<> (set), depth + 1); // 객체 자체를 매개변수로 넘김
DFS(set, depth + 1); // 객체 주소를 매개변수로 넘김

이거에 따라 테스트케이스 3번이 실패하냐 성공하냐로 나뉘었다는 점이었다.
질문하기 게시판에 있는 댓글을 보고 힌트를 얻어 깊은 복사, 얕은 복사 개념 때문이었다는 것을 알게되었고
오늘도 공부할게 정말 많고 갈길이 멀다는 것을 느꼈다.

https://studywithus.tistory.com/116

[JAVA] 깊은 복사(Deep Copy) vs 얕은 복사(Shallow Copy)

또한 HashSet<HashSet<String>> result_set = HashS

    public void DFS(HashSet<String> set, int depth) {
        if (depth == bannedid.length) {
            result_set.add(new HashSet<>(set));
            
            return;
        }

        for (int i = 0; i < userid.length; i++) {
            if (set.contains(userid[i]))
                continue;

            if (check(userid[i], bannedid[depth])) {
                set.add(userid[i]);
                
                DFS(new HashSet<> (set), depth + 1);
                // DFS(set, depth + 1);
                set.remove(userid[i]);
            }
        }
    }

HashSet 안에 HashSet 을 이렇게 선언해준 이유는
불량사용자들의 조합을 Set으로 저장했을 때, 입출력예시 3번 처럼
["frodo", "fradi", "crodo", "abc123", "frodoc"]
["fr*d*", "*rodo", "******", "******"]
아래 불량유저 조건에 해당되는 조합이
[crodo, abc123, frodo, frodoc] 
[crodo, abc123, frodo, frodoc] 
[crodo, abc123, frodo, frodoc] [fradi, abc123, frodo, frodoc] 
[crodo, abc123, frodo, frodoc] [fradi, abc123, frodo, frodoc] 
[crodo, abc123, frodo, frodoc] [crodo, fradi, abc123, frodoc] [fradi, abc123, frodo, frodoc] 
이런 식으로 5개 나오지만 1,2번과 3,4번은 각각 중복되는 하나의 조합이기 때문에 
HashSet에 넣어서 중복을 제거해준 것이다.

HashSet<HashSet<String>> result_set = new HashSet<>();

 

전체코드

import java.util.*;

class Solution {

    static String[] userid;
    static String[] bannedid;
    static int answer = 0;
    
     HashSet<HashSet<String>> result_set = new HashSet<>();

    public int solution(String[] user_id, String[] banned_id) {

        userid = user_id;
        bannedid = banned_id;

        DFS(new HashSet<String>(), 0);

        return result_set.size();
    }

    public void DFS(HashSet<String> set, int depth) {
        if (depth == bannedid.length) {
            result_set.add(new HashSet<>(set));
            
            return;
        }

        for (int i = 0; i < userid.length; i++) {
            if (set.contains(userid[i]))
                continue;

            if (check(userid[i], bannedid[depth])) {
                set.add(userid[i]);
                // new HashSet<> (set) 차이가 뭐지
                
                DFS(new HashSet<> (set), depth + 1);
                // DFS(new HashSet<> (), depth + 1);
                set.remove(userid[i]);
            }
        }
    }

    public boolean check(String str1, String str2) {
        boolean flag = true;

        if (str1.length() != str2.length()) {
            flag = false;
            return flag;
        }

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

        return flag;
    }
}