[SW Expert Academy] 12369. 일련번호 붙이기

SW Expert Academy 12369 문제 링크

SW Expert Academy

 

---

풀이

• 사용할 알파벳이 주어지고 숫자가 주어질 때 , 사전 순으로 해당 숫자 번째의 문자열을 출력하면 되는 문제다.
• 각 자릿수에 들어갈 알파벳을 이전까지의 번호를 보고 정해 최종적으로 합쳐 출력한다.
• 예를 들어 , AB 12의 경우 12는 < 2 + 4 + 8 이므로 3자리 단어다.
• 3자리 단어 이전 까지의 경우는 6 이므로 12 - 6 = 6  즉 3자리 단어만 놓고 보았을 때 6번째 단어다.
• 6번째 단어의 첫번째 자리는 (6-1) // 4 ( 2자리 경우의 수 ) = 1 이므로 알파벳 순서 배열에서 1번인 B가 들어가게 된다.
• 모든 자리에 대해 위 과정을 반복하면 최종 문자열을 구할 수 있다.
•  제한 시간을 의식하고 풀어서 그런지 더 쉽게 풀 수 있는 문제를 어렵게 푼 것 같다.

 

n = int(input())
for i in range(n):
    s , k = input().split(" ")
    s ,k = list(s),int(k)
    ori , p , check = len(s) , len(s) , 1
    s.sort()
    stack = [p]
    while p < k:
        stack.append(stack[-1]*ori)
        p = p + stack[-1]
        check += 1
    if k == p:
        print("#%d %s" %((i+1),s[-1]*check))
    else:
        ans = ""
        k = k - (p - stack[-1])
        for o in range(len(stack)-2,-1,-1):
            ans += s[((k - 1) // stack[o])%len(s)]
            k = k - stack[o]
        ans += s[(k+stack[0]-1)%len(s)]
        print("#%d %s" %((i+1),ans))

---