[LeetCode] 1663. Smallest String With A Given Numeric Value (Swift, Python)

Smallest String With A Given Numeric Value - LeetCode

 

 

풀이 

 앞에서부터 차례대로 문자열을 만들어나간다. 사전순으로 가장 앞에 있는 문자열을 구하기 위해서는 앞의 자리에 최대한 a에 가까운 문자로 만들어야한다. 현재 채워야 하는 자리 이후에 가장 큰 z를 채운다고 가정했을 때 k를 만족할 수 있는지를 따져보면 된다.

 

 예제의 n = 5, k = 73을 생각해보자. 현재 채워야하는 첫 번째 자리를 제외하고 나머지 네 자리를 z(26)으로 채운다고 가정해보자. 26 * 4를 하면 104가 되어 현재 73보다 크므로 첫 번째 자리에 a를 넣어도 문자열을 완성할 수 있다. 그럼 이제 첫 번째 자리에는 'a'가 채워지고 k는 73 - 1 = 72가 된다.

 

 두 번째 자리를 제외하고 나머지 세 자리를 z로 채운다고 가정해보자. 26 * 3을 하면 78이 되어 현재 k인 72보다 크므로 두 번째 자리에 a를 넣어도 문자열을 완성할 수 있다. 두 번째 자리 역시 'a'가 채워지고 k는 72 - 1 = 71이 된다.

 

 세 번째 자리를 제외하고 나머지 두 자리를 z로 채운다고 가정해보자. 26 * 2를 하면 52가 되는데 이는 현재 k인 71보다 작으므로 현재 자리에 a를 넣으면 문자열을 완성할 수 없게 된다. 이때 사전순으로 가장 앞에 있는 문자열을 만들어야 하므로 나머지 자리에는 z를 채운다고 가정하고 세 번째 자리에는 현재 k인 71에서 52를 뺀(나머지 두 자리를 z로 채웠을 때 세 번째 자리에 와야하는 가장 큰 문자) 19에 해당하는 s가 와야한다. 그 후 나머지는 z로 채워넣으면 'aaszz' 문자열이 완성된다.

 

코드

[Swift]

class Solution {
    func getSmallestString(_ n: Int, _ k: Int) -> String {
        var ans: String = ""
        var kk: Int = k
        
        for idx in (0..<n).reversed() {
            // 현재 자리 이후 자리들에 z를 채웠을 때 얻을 수 있는 수
            let maxAfterN: Int = 26 * idx
            
            // 그 수가 k보다 크거나 같다면 현재 자리에 'a'를 넣어도
            // 나머지 자리를 'z'로 채워넣으면 k를 만들 수 있다.
            // 그러므로 현재 자리에 'a'를 넣어주고 k는 a에 해당하는 1을 감소시킨다.
            if maxAfterN >= kk {
                ans += "a"
                kk -= 1
            }
            
            //만약 k보다 작다면 현재 자리에 'a'를 넣으면 k를 완성할 수 없다는 뜻이다.
            // 그러므로 현재 자리에는 나머지 자리에 'z'를 넣었을 때 k를 완성시킬 수 있는
            // 최소한의 문자가 와야 한다.
            else if maxAfterN < kk {
                let value = kk - maxAfterN + 96
                
                ans += String(UnicodeScalar(value)!)
                kk = maxAfterN
            }
        }
        
        return ans
    }
}

 

[Python]

class Solution(object):
    def getSmallestString(self, n, k):
        ans = ''

        while n != 0:
            # 현재 자리 이후 자리들에 z를 채웠을 때 얻을 수 있는 수
            maxAfterN = 26 * (n-1)

            # 그 수가 k보다 크거나 같다면 현재 자리에 'a'를 넣어도
            # 나머지 자리를 'z'로 채워넣으면 k를 만들 수 있다.
            # 그러므로 현재 자리에 'a'를 넣어주고 k는 a에 해당하는 1을 감소시킨다.
            if maxAfterN >= k:
                ans += 'a'
                k -= 1

            # 만약 k보다 작다면 현재 자리에 'a'를 넣으면 k를 완성할 수 없다는 뜻이다.
            # 그러므로 현재 자리에는 나머지 자리에 'z'를 넣었을 때 k를 완성시킬 수 있는
            # 최소한의 문자가 와야 한다.
            elif maxAfterN < k:
                ans += chr(k - maxAfterN + 96)
                k = maxAfterN

            n -= 1

        return ans