파이썬으로 길이 k, 거리 n을 만족하는 사전순 최소 소문자 문자열 찾기

두 개의 숫자 n과 k가 주어졌다고 가정해 보겠습니다. 이때 우리는 길이가 k이면서 거리가 n이 되는, 사전순(lexicographically)으로 가장 작은 소문자 문자열을 찾아야 합니다.

여기서 말하는 거리(distance)는 문자열을 이루는 각 알파벳의 번호를 모두 더한 값입니다. 예를 들어 'a'는 1번, 'b'는 2번, 'y'는 25번, 'z'는 26번입니다.

따라서 입력이 n = 15, k = 3이라면 출력은 "aam"이 됩니다. "aam"의 거리는 1 + 1 + 13 = 15이며, 거리가 15인 길이 3의 문자열 중에서 사전순으로 가장 앞에 오는 문자열이기 때문입니다.

알고리즘 접근 방법

이 문제의 핵심 아이디어는 그리디(Greedy) 방식입니다. 사전순으로 가장 작은 문자열을 만들려면 앞쪽 문자들을 가능한 한 'a'(값 1)에 가깝게 유지하고, 남은 무게를 뒤쪽 문자들에 최대한 몰아주는 것이 유리합니다. 각 문자는 최대 'z'(값 26)까지 커질 수 있으므로, 기본값 1에서 시작해 한 문자당 최대 25만큼 더할 수 있습니다.

구체적인 풀이 단계는 다음과 같습니다.

• 크기가 k인 배열 dist를 만들고 모든 값을 1로 초기화합니다.
• credit := n - k로 설정합니다. (추가로 분배해야 할 무게)
• i := k - 1로 설정합니다. (배열의 마지막 인덱스부터 시작)
• credit > 0인 동안 다음을 반복합니다.
  • val := credit과 25 중 더 작은 값
  • dist[i] := dist[i] + val
  • credit := credit - val
  • i := i - 1
• dist의 각 값 d에 대해 chr(d - 1 + ord("a"))로 문자를 변환한 뒤, 이를 하나로 연결하여 반환합니다.

예제 코드

다음 파이썬 구현을 통해 더 자세히 이해해 보겠습니다.

def solve(n, k):
   dist = [1] * k

   credit = n - k

   i = k - 1
   while credit > 0:
      val = min(credit, 25)
      dist[i] += val
      credit -= val
      i -= 1

   return "".join(chr(d - 1 + ord("a")) for d in dist)

n = 15
k = 3
print(solve(n, k))

입력

15, 3

출력

aam

동작 원리 정리

위 코드에서 먼저 모든 문자를 'a'로 초기화한 상태(합 = k)에서 출발합니다. 그런 다음 목표 거리까지 부족한 만큼(n - k)을 뒤쪽 문자부터 순서대로 채워 넣습니다. 한 문자가 26('z')을 초과하지 않도록 한 번에 최대 25만 더하기 때문에, 결과적으로 앞쪽에는 'a'가 많이 남고 무거운 문자들이 뒤쪽에 배치되어 사전순으로 가장 작은 문자열이 완성됩니다.