파이썬으로 길이 n과 숫자 값 k를 만족하는 사전순 최소 문자열 찾기

문제 개요

두 개의 값 n과 k가 주어졌다고 가정해 봅시다. 우리는 길이가 n이고 숫자 값이 k인 문자열 중에서 사전순(lexicographically)으로 가장 작은 문자열을 찾아야 합니다.

여기서 소문자 알파벳의 숫자 값은 알파벳 순서상의 위치(1부터 시작)를 의미합니다. 즉, 문자 'a'의 숫자 값은 1, 'b'는 2와 같은 식이며, 마지막 문자 'z'는 26입니다. 그리고 소문자로 이루어진 문자열의 숫자 값은 문자열에 포함된 모든 문자의 숫자 값의 합으로 정의됩니다.

예시

입력이 n = 4, k = 16일 때 출력 결과는 "aaam"입니다. 숫자 값이 1 + 1 + 1 + 13 = 16이 되고, 길이 4와 값 16이라는 조건을 만족하는 문자열 중에서 이것이 가장 작기 때문입니다.

풀이 접근 방법

이 문제는 그리디(greedy) 기법으로 효율적으로 해결할 수 있습니다. 풀이 단계는 다음과 같습니다.

• 빈 문자열로 시작합니다.
• n이 0보다 큰 동안 다음을 반복합니다.
  • 현재 위치에 넣을 문자 값 letter를 min(26, k - n + 1)로 결정합니다. 남은 n - 1개의 문자에 최소한 1씩은 배분해야 하므로 현재 위치에는 최대 k - (n - 1)까지 사용할 수 있으며, 알파벳의 특성상 26을 초과할 수 없습니다.
  • letter에 해당하는 알파벳 문자를 문자열에 추가합니다.
  • k에서 letter를 빼고, n에서 1을 뺍니다.
• 반복이 끝나면 문자열을 뒤집어 반환합니다.

이 알고리즘은 문자열을 뒤에서부터 채워 나가기 때문에 큰 문자들이 뒤쪽에 배치되고, 앞쪽에는 가능한 한 'a'가 많이 오게 됩니다. 그 결과 사전순으로 가장 작은 문자열을 얻을 수 있습니다.

구현 예제

아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.

def solve(n, k):
    string = ""
    while n > 0:
        letter = min(26, k-n+1)
        string += chr(letter + ord('a') - 1)
        k -= letter
        n -= 1
    return string[::-1]

n = 4
k = 16
print(solve(n, k))

입력

4, 16

출력

aaam

동작 원리 단계별 살펴보기

n = 4, k = 16일 때 알고리즘이 실제로 어떻게 진행되는지 확인해 보겠습니다.

반복 종료 시 누적된 문자열은 "maaa"이며, 이를 뒤집으면 최종 답인 "aaam"을 얻습니다. 이 알고리즘의 시간 복잡도는 O(n)으로 매우 효율적입니다.