[Programmers Lv.3][불량 사용자][java]

문제 링크

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

프로그래머스

---

조건

[제한사항]

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

 

알고리즘 

userid 는 1~8 크기 → 완전탐색
bannedid 1~userid 크기 이하
사용자 아이디들은 중복되지 않음
모든 경우의 수를 찾고 크기를 리턴
경우의 수를 찾을 때, 해당 경우의 수가 불량 사용자 목록과 같은지 확인

 

전체 코드

package com.example.javaproject3.psstudy;

import java.util.*;

public class Solution64064 {
    HashSet<HashSet<String>> list = new HashSet<>();  // 제제 아이디 목록 경우의 수 저장
    public int solution(String[] user_id, String[] banned_id) {
        list = new HashSet<>();
        permutationID(new LinkedHashSet<>(), user_id, banned_id); // 데이터 추가한 순서대로 저장하기 위해 LinkedHashSet
        return list.size();
    }

    public void permutationID(HashSet<String> hs, String[] user_id, String[] banned_id){
        if (hs.size() == banned_id.length) {  //  불량 사용자 목록 길이와 사용자 아이디의 경우의 수 hashset 사이즈가 같을 때
            if(isBan(hs, banned_id)) list.add(new HashSet<>(hs)); // 불량 사용자 목록과 사용자 아이디 목록이 같다면 list에 저장
            return;
        }
        for (String id : user_id) { // 사용자 아이디를 하나씩 판단하여 경우의 수 조합
            if(!hs.contains(id)){ // hashset 에 해당 아이디가 포함되어 있지 않다면
                hs.add(id); // 해당 아이디 추가
                permutationID(hs, user_id, banned_id);  // 재귀로 호출하여 해당 아이디를 포함하는 경우의 수 판단
                hs.remove(id);  // 해당 아이디 제거
            }
        }
    }

    public boolean isBan(HashSet<String> hs, String[] banned_id) { //  해당 경우의 수가 불량 사용자 목록인지 확인하는 메소드
        int idx = 0;
        for(String userID : hs){
            String banID = banned_id[idx++];
            if (userID.length() == banID.length()) {  // 사용자 아이디 길이와 불량 사용자 아이디의 길이가 같다면
                for (int i = 0; i < banID.length(); i++) {
                    if(banID.charAt(i) != '*' && userID.charAt(i) != banID.charAt(i))  // 해당 index 값이 '*' 이 아니고 user id 와 ban id 의 해당 index 값이 다르면
                        return false;  // false 리턴
                 }
            } else return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Solution64064 solution64064 = new Solution64064();
        System.out.println(solution64064.solution(new String[]{"frodo", "fradi", "crodo", "abc123", "frodoc"}, new String[]{"fr*d*", "*rodo", "******", "******"}));
    }
}