파이썬에서 길이가 k이고 거리가 n인 사전순으로 가장 작은 소문자 문자열을 찾는 프로그램

두 개의 숫자 n과 k가 있다고 가정합니다. 사전순으로 크기가 k이고 거리가 n인 가장 작은 소문자 문자열을 찾아야 합니다. 거리는 알파벳 문자 숫자의 합입니다. 예를 들어 'a'는 1, 'b'는 2, 'y'는 25, 'z'는 26 등입니다.

따라서 입력이 n =15 k =3과 같으면 출력은 "aam"이 됩니다. "aam"은 사전순으로 길이 3의 가장 작은 문자열이고 거리가 1 + 1 + 13 =15이기 때문입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• dist :=k 크기의 배열, 1로 채움
• 크레딧 :=n - k
• i :=k - 1
• 신용 기간 동안> 0, 수행
  • val :=최소 크레딧 및 25
  • dist[i] :=dist[i] + val
  • 크레딧 :=크레딧 - val
  • 나는 :=나는 - 1
• dist의 각 d에 대해 ((d - 1 + "a"의 ASCII 문자))를 결합하고 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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