프로그래머스 코딩테스트 연습 - 불량 사용자 (백트래킹, 정규식)

# 주소

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

프로그래머스

# 문제

문제 설명

개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 사용자라는 이름으로 목록을 만들어서 당첨 처리 시 제외하도록 이벤트 당첨자 담당자인 "프로도" 에게 전달하려고 합니다. 이 때 개인정보 보호을 위해 사용자 아이디 중 일부 문자를 '*' 문자로 가려서 전달했습니다. 가리고자 하는 문자 하나에 '*' 문자 하나를 사용하였고 아이디 당 최소 하나 이상의 '*' 문자를 사용하였습니다.
"무지"와 "프로도"는 불량 사용자 목록에 매핑된 응모자 아이디를 제재 아이디 라고 부르기로 하였습니다.

예를 들어, 이벤트에 응모한 전체 사용자 아이디 목록이 다음과 같다면

응모자 아이디

frodo

fradi

crodo

abc123

frodoc

다음과 같이 불량 사용자 아이디 목록이 전달된 경우,

불량 사용자

fr*d*

abc1**

불량 사용자에 매핑되어 당첨에서 제외되어야 야 할 제재 아이디 목록은 다음과 같이 두 가지 경우가 있을 수 있습니다.

제재 아이디

frodo

abc123

제재 아이디

fradi

abc123

이벤트 응모자 아이디 목록이 담긴 배열 user_id와 불량 사용자 아이디 목록이 담긴 배열 banned_id가 매개변수로 주어질 때, 당첨에서 제외되어야 할 제재 아이디 목록은 몇가지 경우의 수가 가능한 지 return 하도록 solution 함수를 완성해주세요.

[제한사항]

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

---

[입출력 예]user_idbanned_idresult

["frodo", "fradi", "crodo", "abc123", "frodoc"]	["fr*d*", "abc1**"]	2
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["*rodo", "*rodo", "******"]	2
["frodo", "fradi", "crodo", "abc123", "frodoc"]	["fr*d*", "*rodo", "******", "******"]	3

입출력 예에 대한 설명입출력 예 #1

문제 설명과 같습니다.

입출력 예 #2

다음과 같이 두 가지 경우가 있습니다.

제재 아이디

frodo

crodo

abc123

제재 아이디

frodo

crodo

frodoc

입출력 예 #3

다음과 같이 세 가지 경우가 있습니다.

제재 아이디

frodo

crodo

abc123

frodoc

제재 아이디

fradi

crodo

abc123

frodoc

제재 아이디

fradi

frodo

abc123

frodoc

# 문제 해설 및 코드 리뷰

import java.util.*;
class Solution{
    static HashSet<String> hashSet;
    String[] arr;
    boolean[] visit;
    public int solution(String[] user_id, String[] banned_id){
        hashSet = new HashSet<>();
        arr = new String[banned_id.length];
        for(int i = 0; i < banned_id.length; i++){
            arr[i] = banned_id[i].replace("*", ".");
        }
        visit = new boolean[user_id.length];
        dfs(user_id,0, "");
        return hashSet.size();
    }
    public void dfs(String[] user_id, int count, String str){
        if(count == arr.length){
            String[] s = str.split(" ");
            Arrays.sort(s);
            StringBuilder newStr = new StringBuilder();
            for (String value : s) newStr.append(value);
            hashSet.add(newStr.toString());
            return;
        }
        for(int i = 0; i < user_id.length; i++){
            if(!visit[i] && user_id[i].matches(arr[count])){
                visit[i] = true;
                dfs(user_id, count + 1, str + " " + user_id[i]);
                visit[i] = false;
            }
        }
    }
}

정규식을 활용한 문제입니다.

저는 https://coding-factory.tistory.com/529

[Java] 자바 정규 표현식 (Pattern, Matcher) 사용법 & 예제

여기서 자료를 참고하여 풀었습니다.

개발자에게 있어 기본적으로 API를 전달받고 요청하기 위해서는 REST API에 대한 지식이 있어야 합니다.

이 때 정규식이란 형식에 맞는 데이터를 전달하고 조건에 맞지 않는 값들은 따로 처리를 하거나 예외로 보내어 DB에 데이터를 형식에 맞게 저장할 수 있습니다.

예를 들어, 휴대폰 번호를 구글폼에서 입력 받아 저장할 때 어떤 사용자는 010-xxxx-xxxx로 보낼 것이고 어떤 사용자는 010xxxxxxxx이렇게 다양하게 보낼 수 있습니다.

그럴 경우 DB에 저장된 데이터를 조회하면 뒤죽박죽으로 섞이기 때문에 이를 방지하고자 어떤 형식으로 들어오든, 앞의 숫자 11자리만 저장하게 처리하여 개발 효율을 높일 수 있겠습니다.

이 문제를 풀기 위해서 물론 정규식을 꼭 알아야 풀 수 있는건 아니지만 개발 역량에도 밀접된 연관을 보이기도 하고 이 문제가 저에게 좋은 공부가 된 것 같아서 문제 풀이와 참고 자료를 공유합니다.

그리고 자료구조는 HashSet을 썼는데, 이는 중복된 자료를 허용하지 않기 때문에 이것을 사용했습니다.

(물론 TreeMap이나 HashMap을 써서 getOrDefault를 사용하는 것이 더 효율이 좋습니다.)

HashSet으로 한 번 풀어봅시다.

static HashSet<String> hashSet;
String[] arr;
boolean[] visit;
public int solution(String[] user_id, String[] banned_id){
    hashSet = new HashSet<>();
    arr = new String[banned_id.length];
    for(int i = 0; i < banned_id.length; i++){
        arr[i] = banned_id[i].replace("*", ".");
    }
    visit = new boolean[user_id.length];
    dfs(user_id,0, "");
    return hashSet.size();
}

static으로 hashset을 선언하고 백트래킹을 위해 arr배열과 visit배열을 생성합니다.

arr의 크기는 banned_id배열의 크기이고 이 banned_id의 *이 들어간 문자는 모두 .으로 치환하여 arr에 삽입합니다.

여기서 사용될 arr는 나중에 user_id와 비교하기 위한 배열로 쓰일 것입니다.

dfs문을 한 번 보겠습니다.

for(int i = 0; i < user_id.length; i++){
            if(!visit[i] && user_id[i].matches(arr[count])){
                visit[i] = true;
                dfs(user_id, count + 1, str + " " + user_id[i]);
                visit[i] = false;
            }
        }

이후 for문을 통해, user_id의 크기만큼 for문을 돌겠습니다.

여기서부터가 중요한데, visit[i]가 false이고 user_id[i]랑 arr[count]랑 매치되는게 있어야만 백트래킹을 진행할 수 있습니다.

저희가 아까전에 *을 .으로 치환했었던거 기억나시나요?

.은 정규표현식에서 '어떤 문자와도 매칭'됩니다.

그러므로 abcde와 ab.cd.이렇게 입력받을 경우 

c와 . e와 .이 알아서 매칭되기 때문에 결과값은 true가 됩니다.

이후부터는 간단합니다.

visit을 true로 바꾸고 dfs의 count를 1증가, str에 user_id[i]를 붙힙니다.

또한 원복시켜주는 작업은 visit[i]를 false함으로써 순열로서 풀 수 있습니다.

이 문제가 순열인지, 조합인지 잘 구분하시는게 좋은데 수학적으로 조합은 1, 2, 3이나 1, 3, 2나 같은 경우로 얘기할 수 있습니다.

이 문제의 경우 잘 생각해보시면 두 번째에 사용될 user_id가 2번 인덱스이고 세 번째에 사용될 user_id가 3번 인덱스라면 아무리 순서가 바뀌어도 오름차순으로 정렬 후  배열을 보시면 둘 다 1 2 3 이렇게 나열됨을 알 수 있는데요.

그럴 경우 Set에서는 하나의 String으로 인식하기 때문에 String입장에서 보면 조합이 맞습니다.

하지만 배열형태로 봤을 때 우리가 데이터를 담고 user_id를 덧붙혀서 만든 새로운 배열은 어디까지나 순열의 과정에 포함되어 있습니다.

전혀 다른 경우의 수로 인지를 하고 이후에 오름차순으로 바꾸는 것이기 때문에 순열 방법으로 풀되 이후의 정렬을 통해 조합으로 된다 이렇게 생각할 수 있는 것입니다.

if(count == arr.length){
    String[] s = str.split(" ");
    Arrays.sort(s);
    StringBuilder newStr = new StringBuilder();
    for (String value : s) newStr.append(value);
    hashSet.add(newStr.toString());
    return;
}

그러므로 이후의 count가 arr크기만큼 탐색했을 때를 보시면 s라는 배열에 split하여 담은 뒤 정렬 후 새로운 String을 만들고 hashSet에 넣어서 중복된 것이 없게끔 하는 것을 확인할 수 있습니다.

또한 정답을 출력할 때에는 hashSet의 크기만 출력하면 정답이 되는 것을 확인할 수도 있겠습니다.

 

 

문제에 대한 저의 발전 방향을 정리하자면 다음과 같습니다.

1. 순열 문제이지만 조합의 개념을 알아야 한다는 것

2. 백트래킹 방법을 먼저 생각했지만 자료구조가 마땅히 생각이 안났다는 것

3. 정규식에 대해 다시 공부할 수 있었고 정규식으로 푸는 법에 대해 배운 것

4. 정규식으로 안풀 경우 문자열을 하나하나 대조해가며 풀 수 있는데 이럴 경우 for문이 하나 더 필요함.

5. for문을 안 쓸경우 HashSet을 하나 더 쓰는 방법도 존재

6. 문자열 처리는 확실히 어렵다.. 

감사합니다.