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

문제 핵심

주문은 다음 순서로 정렬된다.

a, b, ..., z, aa, ab, ..., zz, aaa, ...

이 순서는 알파벳을 1~26으로 표현하는 숫자 순서와 같다.

a  = 1
z  = 26
aa = 27
ab = 28
az = 52
ba = 53

따라서 주문을 번호로 변환하면 문자열 대신 숫자로 문제를 해결할 수 있다.

왜 <=로 비교할까?

삭제 번호가 목표 번호와 같은 경우에도 목표를 미뤄야 한다.

예를 들어 삭제 전 첫 번째 주문은 "a"다.

n = 1
bans = ["a"]

처음 목표는 1이지만 1번 주문이 삭제되었다.

따라서 삭제 후 첫 번째 주문은 원래 2번 주문인 "b"가 된다.

banned_number = 1
target = 1

1 <= 1이므로 target = 2

그러므로 조건은 <가 아니라 <=여야 한다.

주문을 번호로 변환

알파벳을 다음과 같이 숫자로 대응한다.

a = 1, b = 2, ..., z = 26

def to_number(word):
    number = 0

    for char in word:
        number = number * 26 + (ord(char) - ord("a") + 1)

    return number

예를 들어 "ba"는 다음과 같다.

2 × 26 + 1 = 53

번호를 주문으로 변환

일반적인 26진법과 달리 이 문제에는 0에 해당하는 문자가 없다.

따라서 나머지를 구하기 전에 번호에서 1을 빼준다.

def to_word(number):
    result = []

    while number > 0:
        number, remainder = divmod(number - 1, 26)
        result.append(chr(ord("a") + remainder))

    return "".join(reversed(result))

변환 예시는 다음과 같다.

1   -> a
26  -> z
27  -> aa
52  -> az
53  -> ba
702 -> zz
703 -> aaa

전체 정답 코드

def solution(n, bans):
    def to_number(word):
        number = 0

        for char in word:
            value = ord(char) - ord("a") + 1
            number = number * 26 + value

        return number

    def to_word(number):
        result = []

        while number > 0:
            number, remainder = divmod(number - 1, 26)
            result.append(chr(ord("a") + remainder))

        return "".join(reversed(result))

    banned_numbers = sorted(to_number(word) for word in bans)

    target = n

    for banned_number in banned_numbers:
        if banned_number <= target:
            target += 1
        else:
            break

    return to_word(target)

동작 과정

banned_numbers = sorted(to_number(word) for word in bans)

삭제 주문을 번호로 변환한 뒤 오름차순으로 정렬한다.

target = n

삭제가 없다고 가정했을 때의 목표 번호에서 시작한다.

for banned_number in banned_numbers:
    if banned_number <= target:
        target += 1
    else:
        break

현재 목표 번호 이전 또는 같은 위치의 주문이 삭제되었다면 목표를 한 칸 뒤로 이동한다.

삭제 번호가 목표보다 커지면 이후 삭제 주문도 모두 목표보다 크므로 반복을 종료한다.

return to_word(target)

최종적으로 구한 원래 주문 번호를 문자열로 변환한다.

실행 예제

n = 30
bans = ["d", "e", "bb", "aa", "ae"]

print(solution(n, bans))

실행 결과:

ah

시간 복잡도

삭제 주문의 개수를 B, 주문의 최대 길이를 L이라고 하자.

삭제 주문을 번호로 변환하는 데 다음 시간이 필요하다.

O(B × L)

번호 정렬에는 다음 시간이 필요하다.

O(B log B)

정렬한 삭제 번호는 한 번만 순회한다.

O(B)

따라서 전체 시간 복잡도는 다음과 같다.

O(B × L + B log B)

공간 복잡도는 변환된 삭제 번호를 저장하므로 다음과 같다.

O(B)

정리

이 풀이의 핵심은 삭제 후 n번째 주문이 원래 주문서에서 몇 번째였는지를 직접 추적하는 것이다.

1. 주문을 1부터 시작하는 26진수 번호로 바꾼다.
2. 삭제 번호를 오름차순으로 정렬한다.
3. 목표 번호를 n으로 시작한다.
4. 삭제 번호가 목표 이하라면 목표를 1 증가시킨다.
5. 최종 목표 번호를 다시 주문 문자열로 바꾼다.

삭제 주문 하나가 목표 앞에 있을 때마다 답이 정확히 한 칸씩 뒤로 밀린다는 점이 핵심이다.