[프로그래머스] 불량 사용자 - Java

문제

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

 

---

 

문제 개요

이벤트 응모자 중 특정 패턴과 일치하는 아이디를 불량 사용자로 제재하려고 한다. 응모자 아이디와 불량 사용자 패턴이 주어질 때, 불량 사용자 패턴에 따라 제재될 수 있는 응모자 아이디 목록의 가능한 경우의 수를 구하는 문제이다. 제재 아이디 목록의 순서는 상관없으며, 동일한 내용을 가진 경우는 하나로 간주한다.

 

접근 방법

1. 불량 사용자 패턴 변환:
   • 주어진 불량 사용자 패턴(banned_id)의 * 문자를 정규 표현식의 와일드카드인 .으로 변환하여 매칭 가능한 형태로 변경한다.

이유 및 필요성

1. *는 정규 표현식의 문자가 아님

• 문제에서 주어진 banned_id에는 *가 포함되어 있습니다.
• *는 일반 문자열로써 사용되지만, 정규 표현식에서는 **"이전 문자 0개 이상 반복"**이라는 특별한 의미를 가집니다.
• 예를 들어, 정규 표현식 a*는 "", "a", "aa", "aaa" 등과 일치합니다.

2. *를 정규식의 .와 결합하여 의미 확장

• 문제의 의도는 *가 "임의의 문자 0개 이상"을 뜻하도록 사용되었다고 가정할 수 있습니다.
• 이를 구현하려면:
  • 정규 표현식의 .: 임의의 문자 한 개
  • 정규 표현식의 .*: 임의의 문자 0개 이상과 같은 의미로 바뀌어야 합니다.
• 따라서, 단순히 *를 .로 변환하면 "한 글자와 매칭"하도록 바뀌며, 이는 문제 요구사항과 맞지 않습니다.
• 최종적으로 *는 정규식으로 "임의의 문자 0개 이상"을 의미하는 .*로 변환되어야 합니다.

1. 조합 생성:
   • comb 함수는 불량 사용자 패턴에 따라 가능한 응모자 아이디 조합을 재귀적으로 생성한다.
   • depth를 통해 현재 처리 중인 불량 사용자 패턴을 추적한다.
2. 조합의 중복 제거:
   • 재귀 함수에서 생성된 제재 아이디 목록은 정렬 후 문자열로 변환하여 Set에 저장한다.
   • 이를 통해 동일한 제재 아이디 목록은 하나로 처리된다.
3. 매칭 확인:
   • 정규 표현식을 사용하여 현재 응모자 아이디가 특정 불량 사용자 패턴과 매칭되는지 확인한다(user_id[i].matches(banned_id[depth])).
   • 매칭된 경우 해당 응모자 아이디를 선택하고, 다음 패턴으로 이동한다.

 

코드

import java.util.*;
class Solution {
    static boolean[] v;
    static Set<String> set;
    public int solution(String[] user_id, String[] banned_id) {
        int answer = 0;
        v = new boolean[user_id.length];
        set = new HashSet<>();

        for (int i = 0; i < banned_id.length; i++) {
            banned_id[i] = banned_id[i].replace("*", ".");
        }

        comb(0, "", user_id, banned_id);
        return set.size();
    }
    
        public static void comb(int depth, String s, String[] user_id, String[] banned_id) {
        if(depth == banned_id.length) {
            String[] arr = s.split(" ");
            Arrays.sort(arr);

            String bucket = "";
            for (String a : arr) {
                bucket += a;
            }
            set.add(bucket);
            return;
        }

        for (int i = 0; i < user_id.length; i++) {
            if(!v[i] && user_id[i].matches(banned_id[depth])) {
                v[i] = true;
                comb(depth+1, user_id[i]+" "+s, user_id, banned_id);
                v[i] = false;
            }
        }
    }
}