[programmers/js] 봉인된 주문

봉인된 주문

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

문제 설명

이 문제는 삭제된 주문이 있는 마법 주문서에서 n번째 주문을 찾는 문제입니다. 주문서는 모든 가능한 알파벳 소문자로 구성된 문자열들을 고대의 규칙에 따라 사전순으로 정렬한 것입니다. 이 주문서는 각 문자열의 길이가 1글자부터 11글자 이하까지 존재하며, 글자 수가 적은 주문부터 먼저 기록되고, 길이가 같다면 사전순으로 기록됩니다.

예를 들어, 주문서에서 "d", "e", "bb", "aa", "ae" 5개의 주문을 지웠을 때, 주문서에서 30번째 주문을 찾으려고 합니다.
1~3번째 주문은 "a", "b", "c" 입니다.
"d"와 "e"는 삭제됐으므로 4~24번째 주문은 "f" ~ "z"입니다.
"aa"는 삭제됐으므로 25~27번째 주문은 "ab", "ac", "ad"입니다.
"ae"는 삭제됐으므로 28~30번째 주문은 "af", "ag", "ah"입니다.
따라서 30번째 주문은 "ah"가 됩니다.

풀이

주문을 숫자로 변환
각 주문을 숫자로 변환하는 방법이 필요합니다. 예를 들어, a는 1, b는 2, ..., z는 26이 됩니다. 2글자 주문 aa는 27, ab는 28, 이런 식으로 숫자로 매핑됩니다.

삭제된 주문 처리
삭제된 주문들을 사전순으로 정렬한 후, 삭제된 주문보다 작은 값들에 대해서 n을 증가시켜줍니다. 이렇게 하면 실제 삭제된 주문이 몇 개 있는지를 파악하고, 그만큼 건너뛰어야 할 주문을 계산할 수 있습니다.

최종 주문 계산
n번째 주문을 구할 때, 해당 주문의 순서를 알면 그것을 다시 알파벳 문자열로 변환합니다.

function solution(n, bans) {
    const alpha = 'abcdefghijklmnopqrstuvwxyz'
    // 전체 문자열 중 n번째 주문이 속한 길이를 찾기
    let len = 1;
    while (n > 26 ** len) {
        len++;
    }
    
    const strToIndex = (str) => [...str].reduce((a, c) => a * 26 + (c.charCodeAt(0) - 96), 0);    
    
    // bans 정렬
    bans.sort((a, b) => strToIndex(a) - strToIndex(b));
    
    // 넘기는 갯수 보기
    for (const ban of bans) {
        // 길이가 길면 넘긴다.
        if (ban.length > len) break;
        // n 보다 작은 번호를 가진 ban만 count 증가        
        if (strToIndex(ban) <= n) n += 1;
    }
    
    let answer = "";
    while (len--) {
        answer = alpha[(n - 1) % 26] + answer;
        n = Math.floor((n - 1) / 26);
    }

    return answer;
}

배운점

배열을 숫자로 비교하는 이유
알파벳 문자열을 숫자로 바꾸어 비교하면 문자열의 순서가 숫자처럼 간단하게 비교되기 때문입니다.
예를 들어 문자열의 경우 sort()를 통해 "aa", "a", "b"를 비교하면 => [ 'a', 'aa', 'b' ]가 출력됩니다.
우리는 ['a', 'b', 'aa']를 원해 숫자 변경을 통해 사전순으로 비교할 수 있습니다.

n-1을 하는 이유
우리가 인덱스에 접근할 때, n번째 주문을 구할 때 배열의 인덱스는 0부터 시작하기 때문에 n-1을 해줘야 인덱스와 일치하는 위치의 주문을 구할 수 있습니다.