1663. Smallest String With A Given Numeric Value

[zeikar]

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]