Problem link
https://leetcode.com/problems/smallest-string-with-a-given-numeric-value/
Problem Summary
1: a, 2: b... 26: z 라고 할 때 k를 나타낼 수 있는 n 길이의 사전순으로 가장 작은 문자열을 출력하는 문제.
문자열의 값은 각 자리의 알파벳 수를 더하는 것이다.
Solution
딱 보니 큰 알파벳을 뒤부터 채워나가면 된다. z부터 넣다가 안되면 일반 알파벳, 나머지는 a로 채우면 사전순으로 가장 작게 만들 수 있다. 즉 그리디.
Source Code
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
result = ''
for i in range(n):
x = k - n + i + 1
if x >= 26:
result += 'z'
k -= 26
else:
result += (chr(96 + x))
k -= x
return result[::-1]