[프로그래머스 Level3] 불량 사용자(JAVA) - 2019 카카오 인턴

문제

---

https://programmers.co.kr/learn/courses/30/lessons/64064?language=java

코딩테스트 연습 - 불량 사용자

[제한사항]

• user_id 배열의 크기는 1 이상 8 이하입니다.
• user_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 응모한 사용자 아이디들은 서로 중복되지 않습니다.
  • 응모한 사용자 아이디는 알파벳 소문자와 숫자로만으로 구성되어 있습니다.
• banned_id 배열의 크기는 1 이상 user_id 배열의 크기 이하입니다.
• banned_id 배열 각 원소들의 값은 길이가 1 이상 8 이하인 문자열입니다.
  • 불량 사용자 아이디는 알파벳 소문자와 숫자, 가리기 위한 문자 '*' 로만 이루어져 있습니다.
  • 불량 사용자 아이디는 '*' 문자를 하나 이상 포함하고 있습니다.
  • 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당하고 같은 응모자 아이디가 중복해서 제재 아이디 목록에 들어가는 경우는 없습니다.
• 제재 아이디 목록들을 구했을 때 아이디들이 나열된 순서와 관계없이 아이디 목록의 내용이 동일하다면 같은 것으로 처리하여 하나로 세면 됩니다.

 

 

 

문제풀이

---

 

• user_id 배열의 크기는 1 이상 8 이하. → 매우 작은수로 완탐을 고려해 볼 수 있다.
• banned_id 배열의 크기 1 이상 user_id 크기 이하
• 응모한 사용자 아이디들은 서로 중복되지 않는다.
• 불량 사용자 아이디 하나는 응모자 아이디 중 하나에 해당, 같은 응모자 아이디가 중복해서 제제 아이디 목록에 들어가는 경우는 없다.
• 크기는 불량 사용자 아이디 만큼 유저아이디로 만들 수 있는 경우의 수를 만들어 본다.
• 중복을 제거하기 위해 해시셋을 사용하였다. 추가한 순서를 보장하기 위하여 LinkedHashSet을 사용
• 만들어진 불량 사용자 리스트가, 주어진 불량사용자리스트에 맞는지 확인 해본다.

 

 

 

소스코드

---

import java.util.*;

class Solution {
    static HashSet<HashSet<String>> answer;
    public int solution(String[] user_id, String[] banned_id) {
        answer = new HashSet<>();

        dfs(new LinkedHashSet<>(), user_id, banned_id);

        return answer.size();
    }


    private static void dfs(HashSet<String> hs, String[] user_id, String[] banned_id) {
        if (hs.size() == banned_id.length) {
            if (isBanList(hs, banned_id)) {
                answer.add(new HashSet<>(hs));
            }
            return;
        }

        for (String userId : user_id) {
            if (hs.add(userId)) {
                dfs(hs, user_id, banned_id);
                hs.remove(userId);
            }
        }
    }


    private static boolean isBanList(HashSet<String> hs, String[] banned_id) {
        int idx = 0;
        for (String userID : hs) {
            String banID = banned_id[idx++];
            if (userID.length() != banID.length()) {
                return false;
            }
            for (int i = 0; i < banID.length(); i++) {
                if (banID.charAt(i) == '*') {
                    continue;
                }
                if (userID.charAt(i) != banID.charAt(i)) {
                    return false;
                }
            }
        }
        return true;
    }
}