[LeetCode] 1663 | Smallest String With A Given Numeric Value | Python

---

문제 링크: https://leetcode.com/problems/smallest-string-with-a-given-numeric-value/

---

문제

The numeric value of a lowercase character is defined as its position (1-indexed) in the alphabet, so the numeric value of a is 1, the numeric value of b is 2, the numeric value of c is 3, and so on.

The numeric value of a string consisting of lowercase characters is defined as the sum of its characters' numeric values. For example, the numeric value of the string "abe" is equal to 1 + 2 + 5 = 8.

You are given two integers n and k. Return the lexicographically smallest string with length equal to n and numeric value equal to k.

Note that a string x is lexicographically smaller than string y if x comes before y in dictionary order, that is, either x is a prefix of y, or if i is the first position such that x[i] != y[i], then x[i] comes before y[i] in alphabetic order.

---

조건

• 1 <= n <= $10^5$
• n <= k <= 26 * n

---

내 풀이

문자열의 길이가 n이 되어야하므로 a*n인 문자열을 만든다. (ex. n=3 $\rightarrow$ aaa)

현재까지 문자열의 value의 합은 $1 \times n = n$이므로 k에서 n을 뺀다.

남은 k를 맨 뒤에서부터 차례로 더해주면 된다.

---

코드

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        ans = [1 for _ in range(n)]
        
        k -= n
        while k > 0:
            if k > 25:
                ans[n-1] += 25
                k -= 25
            else:
                ans[n-1] += k
                k = 0
            n -= 1
        
        ans = [chr(ans[i]+ord('a')-1) for i in range(len(ans))]
        
        return ''.join(ans)