[JS] 불량 사용자: 정규 표현식을 내 맘대로 써보자!

정규 표현식을 물어보는 문제가 가끔씩 있더라구요.매번 검색해서 어떻게 어떻게 해내긴 했는데 한 번 다뤄보는게 좋을 것 같습니다.

 

이 문제가 딱 그렇게 다루기 좋아보여서 가져와봤습니다.

---

정규 표현식

Javascript에선 주로 string 형식의 문자열에서 원하는 값이 있는지 찾기 위해서 사용합니다.

일반적으로 웹에서 이메일 형식의 input을 받는다던가, password에 특정 규칙을 만족하는지 등에서 쓰입니다.

 

다만, 코딩테스트에서 다루는 정규 표현식의 성격은 약간 다를 수 있을 것 같습니다.

보통 이런 식으로 묻는 경우가 많습니다. 

 

어떤 특정 자리에 이 문자가 들어가는지?
이 자리에 모든 문자가 올 수 있을 때 만족하는 문자는?

 

이스케이프 문자를 다 외우는 건 약간 비효율적인 것 같습니다. 검색하면 다 나오니까요

(이스케이프 문자는 특정 특수문자로 특정 상황을 캐치해낼 수 있습니다. \s => 공백 문자, \d => 숫자 이런식으로요)

 

다만, 위의 두 개 정도는 편의를 위해서 이해해두면 편합니다.

그 전에 당연하게 모든 문제가 정규표현식에 맞는 형태로 줄 리가 없으니.. 일반적으론 replace를 이용해서 원하는 형태로 가공합니다.

 

0. replace를 이용한 전역 문자 치환

```
app*라는 문자열가 있다고 합시다.
*의 뜻은 뒤에 영문 대,소문자 형태로 어떤 문자가 0개 이상 올 수 있다는 뜻입니다.
예를 들어, apple, application, approach 등 모든 단어가 해당됩니다.
```
const sample = [apple, application, approach, afford, episode];
const input = "app*";
const regex = new RegExp(input.replace(/*/g, "[A-Za-z]{0,Infinity}");

sample.filter(v => regex.test(v));
// => [apple, application, approach];

이런 식으로 replace를 이용해 줍시다.

replace의 첫 번째 인자는 string이 오면, 앞에서부터 읽어서 딱 하나만 바꿔주는데요.

저런 식으로 /원하는 문자열/g 형식으로 지정해놓으면 모든 문자 중에 해당 부분을 치환해줍니다.

 

1. 특정 자리에 문자가 있는지 판별하는 방법

위의 예시코드처럼 예시의 구분문자를 정규표현식으로 바꿔줍니다.

// 영문대문자, 영문 소문자, 숫자, 한글이 1개 있는지?
const regex = /[A-za-z-0-9가-힣]{1}/

// 마찬가지의 문자가 3개 이상 5개 이하로 있는지?
// 보통 전화번호나 이메일 같은거에 씁니다.
const regex = /[A-za-z-0-9가-힣]{3, 5}/

 

보통 문자열을 다루는 경우가 많아서 저런 식으로 /[_____]/ 이런 형태안에 원하는 문자를 저렇게 넣어주거나,

new RegExp("____ ") 이 안에 원하는 문자를 넣어주면 정규표현식으로 쓸 수 있습니다.

 

2. 정규표현식의 활용: test | match

정규표현식을 활용할 때는 주로 test나 match를 사용합니다.

test와 filter를 함께 사용하면 match도 표현 가능하기 때문에 사실 어떤 걸 써도 원하는 형태로 가공은 됩니다.

전 test를 주로 사용해요.

const sample = ["apple", "banana", "010" "Ny4U"];
const regex = /[a-z]/{1};

const result0 = sample.map(v => regex.test(v));
// result => [true, true, false, true];

const result1 = sample.filter(v => regex.test(v));
// result1 => ["apple", "banana", "Ny4U"];

 

이 정도 했으면 이번 문제는 충분히 풀만 하겠네요.

같이 한 번 볼까요?

문제 요약

이벤트에 응모한 유저 중 불량 유저를 걸러내려고 합니다.

불량 유저의 경우 다음과 같이 전달됩니다.

불량 사용자

fr*d*

abc1**

* 문자는 해당 자리에 1글자가 올 수 있다는 뜻을 의미합니다.

제한사항

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

테스트케이스

user_id	banned_id	return
["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

 

접근 방법

적절하게 정규표현식을 사용했다면, 조건에 맞는 id를 걸러내는 건 어렵지 않습니다.

다만, 정규표현식으로 글자 수까지 정확히 걸러낼 수는 없습니다.

"frodofrodo" 라는 글자가 있다면 "fr*d*" 라는 조건으로 검색된다면 같이 검색되게 되는거죠.

그러니 글자 수는 length로 따로 제한을 주도록 합시다!

 

성공적으로 문자를 분류해 냈다면, dfs로 탐색을 해봅시다!

자 그럼 정답을 봐볼까요?

 

정답 코드

function solution(user_id, banned_id) {
    const banMap = new Map();
    let index = 0;
    
    for (const id of banned_id) {
        const targets = user_id.filter(v => {
            if (v.length !== id.length) return false;
            return new RegExp(`${id.replace(/\*/g, "[a-z0-9]{1}")}`).test(v)
        });
        banMap.set(`${id}${index}`, targets);
        index++;
    }
    
    const combinations = [...banMap.values()];
    const n = combinations.length;
    const result = new Set();
    dfs("", 0);

    return result.size;
    
    function dfs(usrStr, level) {
        if (level === n) {
            const usrPair = [...new Set(usrStr.split(","))];
            if (usrPair.length !== n) return;
            
            result.add(usrPair.sort().join());
            return;
        }
        for (const id of combinations[level]) {
            // 이거 왜이러는지 아시는분...? 그냥 id로 하면 안되더라구요.
            if (usrStr.includes(id + ",")) continue;
            dfs(usrStr + (usrStr.length === 0 ? "" : ",") + id, level + 1);
        }
    }
}

실행 결과

5번...ㅋㅋㅋㅋㅋ

팁 1. 왜 dfs를 string으로 했나요?

저는 result를 set으로 관리해서 중복을 제거했습니다.

배열 depth가 생기면 중복 관리를 못해주기 때문에 string으로 넣었는데... 생각해보니 그냥 배열로 돌린다음에 나중에 join()해서 넣어줘도 되었겠네요. 그냥 관성적으로 했다고 생각해주세요

 

팁 2. 테스트케이스 5번이 통과가 안되요.

for (const id of combinations[level]) {
    if (usrStr.includes(id + ",")) continue;
    dfs(usrStr + (usrStr.length === 0 ? "" : ",") + id, level + 1);
}

 

dfs에서 뭔가 가짓수가 많나봅니다. 이럴 땐 가지를 좀 줄여주는게 효과적이겠죠.

반복을 딱 banned_id의 갯수만큼 해주기 때문에 중복값이 들어가는 순간 버리는 가지가 됩니다.

for문을 돌때 그런 값이 있다면 loop를 타지 않도록 continue를 넣어줍시다.

(다만, 이유는 모르겠지만, 저처럼 string으로 태우시는 분들은 그냥 id만 넣으면 인식을 못하더라구요. 구분자까지 같이 넣어주셔야 인식이 됩니다.)

 

정규표현식만 알면 쉽게 풀 수 있는 문제였습니다.

그럼 이만!