[Lv.3] 불량 사용자 : Java

프로그래머스

 

 

 

이해하기

머리로는 이해가 되는데 어떻게 구현해야할지 감이 안 잡혔던 문제...

찾아보니 생각보다 쉽게 풀 수 있어서 허탈했다ㅜㅅㅜ

 

이번에 참고한 블로그는 요기

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

 

• dfs(백트래킹) 사용
• 불량 아이디 별로 조건에 만족하는 아이디를 HashSet에 넣어줌
• 이 때 서로 같은 메모리를 가리키지 않도록 매 단계마다 깊은 복사할 것
• 모든 불량 아이디가 채워지면 result에 담을 것
• result.size() 반환

 

문제풀이

import java.util.*;

class Solution {
    String[] userIdArr;
    String[] bannedIdArr;
    boolean[] visited;
    HashSet<HashSet<String>> result = new HashSet<>();

    public int solution(String[] user_id, String[] banned_id) {
        userIdArr = user_id;
        bannedIdArr = banned_id;
        visited = new boolean[userIdArr.length];

        dfs(new HashSet<>(), 0);

        return result.size();
    }

    public void dfs(HashSet<String> set, int depth) {
        if (depth == bannedIdArr.length) {
            result.add(set);
            return;
        }

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

            if (check(userIdArr[i], bannedIdArr[depth])) {
                set.add(userIdArr[i]);
                dfs(new HashSet<>(set), depth + 1);
                set.remove(userIdArr[i]);
            }
        }
    }

    public boolean check(String userId, String bannedId) {
        if (userId.length() != bannedId.length()) {
            return false;
        }

        boolean match = true;

        for (int i = 0; i < userId.length(); i++) {
            if (bannedId.charAt(i) != '*' && userId.charAt(i) != bannedId.charAt(i)) {
                match = false;
                break;
            }
        }
        return match;
    }
}

 

        userIdArr = user_id;
        bannedIdArr = banned_id;
        visited = new boolean[userIdArr.length];

        dfs(new HashSet<>(), 0);

        return result.size();

 

user_id와 banned_id를 복사하고, visited를 선언한다.

dfs의 파라미터로 HashSet과 depth = 0을 넘긴다.

 

    public void dfs(HashSet<String> set, int depth) {
        if (depth == bannedIdArr.length) {
            result.add(set);
            return;
        }

 

dfs 함수 내에서 depth가 bannedIdArr.length와 같아졌다는 것은 끝까지 탐색하였다는 뜻이므로 result.add(set)해주고 리턴한다.

 

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

            if (check(userIdArr[i], bannedIdArr[depth])) {
                set.add(userIdArr[i]);
                dfs(new HashSet<>(set), depth + 1);
                set.remove(userIdArr[i]);
            }
        }

 

아니라면 밑으로 내려와서 for문 내부를 실행한다

userIdArr를 순회하며 만약 set에 이미 userIdArr[i]가 포함되어 있다면 넘어간다.

 

만약 아직 set에 포함되어 있지 않다면 check 함수를 통해 서로 매치되는지 확인한 후, true라면 set.add(userIdArr[i]) 해주고 dfs의 파라미터로는 set과 depth + 1을 넘겨준다.

백트래킹을 위해 set.remove(userIdArr[i]) 해준다.

 

    public boolean check(String userId, String bannedId) {
        if (userId.length() != bannedId.length()) {
            return false;
        }

        boolean match = true;

        for (int i = 0; i < userId.length(); i++) {
            if (bannedId.charAt(i) != '*' && userId.charAt(i) != bannedId.charAt(i)) {
                match = false;
                break;
            }
        }
        return match;
    }

 

check 함수는 다음과 같다.

서로 길이가 다르다면 match될 수 없으니 바로 false 리턴

 

bannedId.charAt(i)가 *가 아닌데도 불구라고, (and) 서로 다르다면 이는 match될 수 없음을 나타내므로 false를 리턴하도록 한다.

 

조건을 전부 만족한다면 return true

 

 

 

쭉 정리해보았는데도 이해가 안 된다... 꼭 다시 풀어볼 것! ㅜㅅㅜ