[프로그래머스] LV.3 불량 사용자 (JS)

KG·2021년 5월 2일

알고리즘

목록 보기

38/61

문제

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

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

제한

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

입출력 예시

user_id	banned_id	result
["frodo", "fradi", "crodo", "abc123", "frodoc"]	`["frd", "abc1**"]`	2
["frodo", "fradi", "crodo", "abc123", "frodoc"]	`["rodo", "rodo", "******"]`	2
["frodo", "fradi", "crodo", "abc123", "frodoc"]	`["frd", "rodo", "***", "****"]`	3

풀이

2019 카카오 개발자 겨울 인턴십 문제에서 출제된 문제이다. 카카오답게(?) 문자열을 다루는 문제이다. 문자열을 다루는 방법은 단순비교부터 배열로 변환하여 검사하는 등 방법은 많지만 여기서는 정규식을 이용해 걸러보자. 정규식은 어느 분야에서나 공통적으로 많이 쓰이니 익혀두면 언젠가는 분명 쓸 일이 있을 것이다.

접근방법

banned_id에 걸러야 할 아이디 키워드가 주어진다. 해당 목록을 가지고 주어진 user_id에서 키워드에 해당하는 아이디를 고를 수 있는 경우의 수를 찾아야 한다. 위 예시에서 요구하는 경우의 수를 찾아야 한다는 것은 결국 조합(Combination)을 구하는 것과 같다. 제재할 아이디의 순서는 상관이 없기 때문이다. 즉 A와 B라는 유저가 있을때, [A, B] 와 [B, A]는 모두 동일한 제재 리스트로 취급한다. 조합을 구하는 방법은 다른 포스트에서도 소개한 것 처럼 여러 방법이 있지만 여기서는 DFS를 이용해서 구해보도록 하자. 일반적인 모든 경우의 수의 목록을 구하는 것이 아닌 단순한 개수를 구하기 때문이기도 하고, 특별한 조건에 부합할 때만 탐색이 이루어지기 때문에 적절한 가지치기를 위해 DFS로 구현해보자. 먼저 여기서 말하는 특별한 조건이란 아래와 같다.

문자열 일치여부 검사

경우의 수를 구성하기 위해서는 banned_id에서 주어진 리스트 목록과 일치하는 아이디만 선택해야 한다. 따라서 주어진 제재 아디이 키워드와 일치하는 유저를 검사하는 함수를 하나 만들어주자.

정규식을 이용해서 만들어 줄 건데, 정규식에 대해 자세히 모른다면 해당 문서를 참고하자. 참고로 본인 역시 정규식의 모든 문법을 달달 외우고 있는것은 아니라서 정규식을 이용할 때 마다 해당 페이지나 다른 문서를 참고하여 짜곤한다.

문제에서 제시하는 제재 리스트를 가지고 다음의 순서에 따라 이에 부합하는 유저 아이디를 찾을 수 있다.

제재 리스트의 길이 === 유저 아이디의 길이
제재 리스트 문자열 === 유저 아이디 문자열
2-1. *는 모든 문자와 일치
2-2. 그 외엔 두 개의 문자가 정확히 일치해야 함

이와 같은 규칙을 정규식으로는 다음과 같이 간단히 만들어줄 수 있다. 만약 다른 방법을 사용했다면 조금 더 로직을 복잡하게 구성했어야 할 것 이다.

다만 정규식의 경우 데이터의 크기가 클 수록 시간이 오래걸릴 수 있다. 대부분 코딩테스트에서는 정규식 로직에 부하가 걸릴 정도의 큰 규모의 말뭉치가 주어지는 경우는 없지만 이 점을 유의하도록 하자!

const match = (user_id, banned_id) => {
  // 기존 문자열의 *를 .으로 대체
  // 정규식의 * 또는 . 과 같은 기호들은 제각각 용도가 정해져 있다.
  // .의 경우는 모든 단일 문자와 대응하는 의미이다.
  // *의 경우는 0회 이상 연속 반복되는 부분과 대응된다.
  // 따라서 우리가 필요한 의미는 .과 같으므로 이로 대체해주고 있다.
  const pattern = banned_id.replace(/\*/g, '.');
  // ^와 &는 각각 시작과 끝을 의미한다.
  // 위에서 만들어준 패턴과 정확히 일치(길이 포함)하는 정규식을 생성한다.
  const regex = new RegExp("\^(" + pattern + "/)$");
  // 생성한 정규식에 부합하는 아이디라면 true 아니면 false를 반환
  return regex.test(user_id);
}

DFS 로직 구성

위 정규식 검사 함수를 통해 제재 리스트에 해당하는 유저 아이디를 걸러줄 수 있다. 해당 아이디를 발견하면 이를 root로 삼아 다음 아이디를 차례대로 탐색하도록 하자. 그러면서 다음의 아이디가 정규식에 의해 걸러지는지 체크를 하도록 해주자. 위의 과정을 각 문자열마다 반복해주면 될 것 이다. 이를 위해 별도의 그래프 연결리스트를 만들어줄 필요는 없다. 선택한 노드를 기준으로 나머지 문자열을 모두 연결된 노드라고 가정하고 DFS 탐색을 진행하면 된다. 따라서 기존에 주어진 user_id와 banned_id를 가지고 다음의 로직으로 DFS 함수를 만들어 주면 그래프 정보 없이 DFS 탐색을 수행할 수 있다.

DFS 함수의 인자로 user_id, banned_id, 현재 deps에서의 제재 아이디 목록, 전체 제재 아이디 목록을 담을 배열을 전달
0부터 user_id 길이까지 반복 진행
현재 유저 아이디와 제재 목록이 일치하는지 검사(=> 방문여부 검사와 동일)
일치한다면 DFS 재귀 호출
4-1. 인자로 전체 제재 아이디 목록을 담을 배열은 그대로 전달하고 그외 나머지는 현재 아이디를 제외한 유저 아이디 목록, 이전에 사용한 제재 키워드를 제외한 제재 목록, 기존 제재 목록 + 현재 아이디로 전달
banned_id의 길이가 0이 되면 전체 제재 목록 배열에 현재 제재 목록 배열을 푸시

말로 풀어쓰면 오히려 어렵게 보인다. 직접 코드를 통해 하나씩 살펴보자.

const dfs = (user_id, banned_id, bans, arr) => {
  // banned_id는 dfs 재귀 호출마다 1씩 크기가 줄어든다
  // 0이 되는 순간은 모든 제재 리스트로 구성을 마쳤다는 의미이므로
  // 현재 단계에서 저장된 유저리스트 bans를 푸시
  if(banned_id.length === 0) arr.push(bans);
  else {
    // 유저 아이디 각각을 root 노드로 삼아 dfs 탐색
    for(let i = 0; i < user_id.length; i++) {
      // 현재 유저아이디와 현재 제재 리스트가 일치하면
      // 제재 리스트는 크기가 앞에서부터 1씩 줄어드므로
      // 인덱스 0으로 접근하면 항상 새로운 제재 아이디에 접근가능
      if(match(user_id[i], banned_id[0])) {
        // 현재 유저아이디를 제외한 유저 리스트 전달
        // 제재 리스트는 앞에서부터 제거하여 전달
        // 현재 제재 목록에 현재 유저아이디 추가
        dfs([...user_id.slice(0, i), ...user_id.slice(i+1)], banned_id.slice(1),
            [...bans, user_id[i]], arr);
      }
    }
  }
}

경우의 수 계산

위의 DFS 함수를 통해 각 경우의 수 목록까지 구할 수 있다. 여기서 우리가 필요한 건 각 목록 구성 요소가 아닌 단순한 개수이기 때문의 해당 배열의 크기를 리턴해주면 될 것 이다. 이때 주의해야 할 점은 위에서 별도로 그래프 연결 리스트를 생성해주지 않고 현재 문자열만 제외한 후 나머지 문자열을 다시 연결된 노드로 전달해주었기 때문에 중복값이 들어가 있다. 하지만 우리가 구하는 값은 조합의 경우의 수이므로 이러한 중복값을 제거해 주어야 한다.

위에서 링크를 건 조합 및 순열 관련 포스트를 참고하면, 사실 DFS 로직에서 구한 경우의 수는 순열을 구하는 로직과 동일하다. 자기자신을 제외한 모든 문자열을 다시 전달하기 때문이다. DFS 에서 순열의 공식으로 경우의 수를 구한 이유는 제재 리스트에 예시 2번처럼 중복된 제재 키워드가 들어있을 수 있기 때문에 이 경우까지 모두 고려해주기 위함이다.

하지만 최종적으로 리턴해주어야 하는 것은 조합의 경우의 수이다. 즉 우리가 DFS 함수를 통해 구한 결과값을 오름차순 또는 내림차순으로 정렬하고 이를 Set 자료구조를 이용해 중복값을 제거해준다면 이 경우의 수를 구할 수 있을 것 이다.

// 전체 순열을 담을 배열
const perms = [];
// dfs 함수 호출
// 여기서는 외부에 dfs 함수를 구현하여 user_id와 banned_id를 인자로 전달해주지만
// 내부에 구현해주면 굳이 이럴 필요는 없다.
dfs(user_id, banned_id, [], perems);
// perms에는 각 유저 아이디가 배열의 형태로 저장
// 따라서 각각의 배열을 오름차순 정렬 후 하나의 문자열로 만들어
// Set 자료구조로 변환하면 중복값을 걸러줄 수 있다.
return new Set(perms.map(perm => perm.sort().join(''))).size;

전체코드

문자열을 처리하는 로직과, DFS로 접근해야 겠다는 점을 파악했다면 쉽게 풀 수 있는 난이도의 문제였던 것 같다. 주석을 제외한 전체 코드는 다음과 같다.

function solution (user_id, banned_id) {
  const perms = [];
  dfs(user_id, banned_id, [], perms);
  return new Set(perms.map(perm => perm.sort().join(''))).size;
}

const dfs = (user_id, banned_id, bans, arr) => {
  if(banned_id.length === 0) arr.push(bans);
  else {
    for(let i = 0; i < user_id.length; i++) {
      if(match(user_id[i], banned_id[0])) {
         dfs([...user_id.slice(0, i), ...user_id.slice(i+1)], banned_id.slice(1),
             [...bans, user_id[i]], arr);
      }
    }
  }
}

const match = (user_id, banned_id) => {
  const pattern = banned_id.replace(/\*/g, '.');
  const regex = new RegExp("\^(" + pattern + "\)$");
  return regex.test(user_id);
}