22.01.08 - [PG] 불량 사용자

[suhyunsim]

문제

• 불량 사용자

핵심 아이디어

• 배열 크기가 8개 -> 브루트포스로도 가능
• user_id 배열에서 banned_id 배열 크기만큼 뽑아서 불량인지 체크, 불량이면 LinkedHashSet에 넣고 그 사이즈만큼을 리턴

어려운 점, 실수

• 처음엔 브루트포스로 풀었는데 결국 중복되는 값들을 줄이는 방법을 구하지 못했음(아마 LinkedHashSet을 활용했으면 풀었을지도?)
• 브루트포스 말고 DFS를 활용한 풀이를 참고

풀이

package main.java.com.poogle.PG.Q64064;

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class Solution {

    private static Set<Set<String>> result;

    public static void main(String[] args) {
        System.out.println(solution(new String[]{"frodo", "fradi", "crodo", "abc123", "frodoc"}, new String[]{"fr*d*", "abc1**"}));
        System.out.println(solution(new String[]{"frodo", "fradi", "crodo", "abc123", "frodoc"}, new String[]{"*rodo", "*rodo", "******"}));
        System.out.println(solution(new String[]{"frodo", "fradi", "crodo", "abc123", "frodoc"}, new String[]{"fr*d*", "*rodo", "******", "******"}));
    }

    public static int solution(String[] user_id, String[] banned_id) {
        result = new HashSet<>();
        dfs(user_id, banned_id, new LinkedHashSet<>());
        return result.size();
    }

    private static void dfs(String[] user_id, String[] banned_id, Set<String> set) {
        if (set.size() == banned_id.length) {
            if (isBanned(set, banned_id)) {
                result.add(new HashSet<>(set));
            }
            return;
        }
        for (String user : user_id) {
            if (!set.contains(user)) {
                set.add(user);
                dfs(user_id, banned_id, set);
                set.remove(user);
            }
        }
    }

    private static boolean isBanned(Set<String> set, String[] banned_id) {
        int i = 0;
        for (String user : set) {
            if (!isSameString(user, banned_id[i++])) return false;
        }
        return true;
    }

    private static boolean isSameString(String user, String ban) {
        if (user.length() != ban.length()) return false;
        for (int i = 0; i < user.length(); i++) {
            if (ban.charAt(i) == '*') continue;
            if (user.charAt(i) != ban.charAt(i)) return false;
        }
        return true;
    }

}