[JS] 프로그래머스 봉인된 주문

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

프로그래머스

 

이 문제는 시간 복잡도는 비슷하지만

코드 길이를 줄일 수 있는 문제였다.

 

그리고 C++로 풀지 않음에 감사했다. (Python이 더 좋다.)

다시 JS로 돌아와서!

제약조건에 있는 수로는 오버풀로가 일어난다.

(Number는 -(2^53 -1) ~ 2^53 - 1까지 이므로 약 10^16까지 된다.)

 

따라서 안전하게 BigInt로 바꾸었다.

(여기서 알아둘 것은 Number + BigInt하면 자동으로 형을 변환하지 않기 때문에 TypeError가 발생한다.)

 

풀이과정은 아래와 같다.

 

먼저 사전순의 규칙을 파악했다.

a, b, c, ... , z

aa, ab, ..., zz

이렇게 하는 것을 보니 26^(문자열의 길이)를 파악했고 여기서 26진법임을 확인했다. 

 

그 다음에 구현 방향을 정했다.

1. n을 알파벳으로 바꾸어서 bans를 순회하며 확인

2. bans를 숫자로 바꾸어서 n과 확인

 

위의 방식을 도출한 이유는 n번째 순서로 도출된 알파벳이 bans보다 앞에 있으면 그만큼 n번째 순서를 갱신(n += 1)해야 하기 때문이다.

 

1번을 하는 경우 많이 복잡해진다.

(n 알파벳 변경 -> 두 개의 길이 확인 -> 길이가 같다면 투 포인터로 같은 인덱스 확인)

즉 n 알파벳과 bans 안의 원소를 비교하면서 계속 순회해야 한다.

 

2번의 경우 비교적 깔끔하다.

(bans 순회하면서 숫자로 변경 -> 숫자 순으로 sort -> 순차적으로 n과 비교해서 n보다 작거나 같으면 n += 1, 아니면 break)

 

따라서 2번을 채택했다.

이때 주의해야 할 것이 sort((a, b) => a - b)는 Number 기준이므로 sort((a, b) => a > b ? 1 : (a < b ? -1 : 0)) 이렇게 표현해야 한다.

 

/* 지금부터는 고민한 과정이다.*/

알파벳 -> 숫자, 숫자 -> 알파벳 변환은 쉬웠다. (공식문서만 봐도 바로 알 수 있다.)

그러나 26진법을 알파벳으로 변환할 때 엣지케이스가 쉽지 않았다.

 

26진법인 경우 0 ~ 25 : 0-index이다

알파벳 순서는 1-index이다. (첫 번째부터 시작하므로)

 

알파벳을 26진법으로 표현한다면 a : 1, b : 2, ... , z : 26이 되어 z는 그 다음 자릿수에 기록된다.

(다르게 표현하자면 a 첫 번째, b 두 번째, ..., z 26번째, z : 10)

 

그러나 최종적으로 n의 알파벳을 구할 때

문자열의 각 칸마다 26으로 나눠야 하고 이 경우

z : 0, a : 1, b : 2, ... 이 되는 이상한 사태가 벌어진다.

 

따라서 이를 방지하기 위해 모든 것을 한칸씩 앞으로 땡겼다.

(n - 1) 그러면 해결된다.

0-index

a : 0, b : 1, ... , z: 25

 

왜 이렇게 해야 하냐고? 그것은 순서(1-index)와 26진법(0-index)가 다르기 때문이다.

순서에는 0번째 순서가 없고 먼저 순서를 구해서 n과 비교해야 하기 때문에 1-index로 변환하고

최종적으로 나온 n을 알파벳으로 표현할 때는 26진법인 0-index으로 변환해야 했다.

 

해당 부분이 가장 어려웠다.

나머지는 C++이 아니니까 BigInt만 잘 고려하면 된다.

 

추가로

26진법은

num = num * 26 + 나머지

이런식으로도 표현할 수 있다. 알아두자.

 

// 알파벳 소문자 26개

const charToIdx = (char) => {
    return BigInt(char.charCodeAt(0) - 97 + 1);
}

function solution(n, bans) {
    let target = BigInt(n);
    
    let banNumbers = bans.map(ban => {
        let num = 0n;
        
        for (let i = 0; i < ban.length; i++) {
            num = num * 26n + charToIdx(ban[i]);
        }
        return num;
    }).sort((a, b) => (a < b ? -1 : (a > b ? 1 : 0)));
    
    for (const num of banNumbers) {
        if (num <= target) {
            target++;
        } else {
            break;
        }
    }
    
    let answer = '';
    while (target > 0n) {
        target--;
        
        let rem = Number(target % 26n);
        answer = String.fromCharCode(rem + 97) + answer;
        
        target = target / 26n;
    }
    
    return answer;
}