2021-01-28] Smallest String With A Given Numeric Value

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/582/week-4-january-22nd-january-28th/3619/

 

주어지는 n,k로 문자열을 만들어 주는 문제이다.

 

문자열의 법칙은 아래 예시를 보며 이해해보자.

 

예시 1번을 보면 n은 3 , k는 27이다. n은 문자열의 길이를 말하는 것이고, k는 이로 만들수 있는 사전정렬(알파벳순)의 가장 앞 순서의 문자열을 말하는 것이다.

 

문제에서 처럼 a=1,b=2,c=3 ..... z=26의 숫자를 갖는다. 총 알파벳이 26자이기 때문이다.

 

k= 27일때 3개의 수로 표현한다면, 1+1+25가 될 수 있다. 물론 1+2+24 등도 되지만, 앞에 제약조건으로 사전 정렬상

가장 앞에 나올수 있는 문자열이 나와야하기에, 1+1+25가 되면 'aay'가 나온다.

 

나는 이것을 보고 26을 나눠 몫과 나머지로 표현 할 수 있다고 생각했다.

 

27을 26으로 나누면, 몫과 나머지는 1,1 이 나온다. 몫의 값은 'z'의 개수로 나머지의 값을 알파벳으로 표현하면 된다.

 

그렇다면 1+26 = 'az' 이렇게 2개의 문자열이 나온다. 여기서 주어진 n과 비교하며 뒤에 부족한 길이만큼 a를

만들고, z에서 부터 a까지 내려온다. a( =1 ) 미만이 될 시엔 그 뒤의 z를 내리고, 다시 z로 돌아가면 된다.

즉 'a'+'ay'가 되어  'aay'가 정답이 된다.

 

이렇게 생각해서 예시 2번도 풀어보면,

 

n=5 / k= 73

몫 = 73//26 =2  나머지 = 73%26 = 21

문자열의 길이는 5이고, 현재 만들어진 문자열은 21+26+26 = 'uzz' 그렇다면, 2개의 문자열을 추가하고

앞의 'u'에서 숫자를 내려본다.

 

1+1+19+26+26 = 'aaszz' 

 

대략적인 알고리즘은 나온 것 같다.

 

숫자와 문자를 매핑하기 위해 ( ex 'a'=1 ) ascii 코드를 사용하였다.

 

문제풀이)

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        ans=""
        mod=int(k%26)
        div=int(k//26)
        if n >= div+1:
            for i in range(n-(div+1)):
                ans+='a'
                if mod==0:
                    ans+='a'
                    mod=25
                    div-=1
                mod-=1
            if mod == 0:
                ans+='a'
                mod=25
                div-=1
            ans+=chr(mod+96)    
        else:
            if mod!=0:
                ans+=chr(mod+96)
        if div>=0:
            for i in range(div):
                ans+='z'
        return ans