BOJ #17828

LEVEL :

Gold5

문제 요약 :

X라는 정수를 만들기 위한 문자열을 형성하는데, 해당 정수를 만족하는 사전순으로 가장 빠른 문자열을 찾아라

해결 방안 :

뭐 일단, 문제를 보고 가장 먼저 든 생각은 시간복잡도 O(N) 안에 풀 수 있겠다라는 생각이었다.
먼저 "A" = 1 이기에 1로 가득 채운 배열로 부터 시작하여 배열의 맨 마지막에서 부터 조정해 나간다. X라는 타켓 정수에 현재 배열의 sum을 빼서 25 보다 크냐 혹은 작거나 같냐를 따져가며 for 문을 진행시켜 X == 배열의 sum 이 같아지는 순간을 catch한다.
결과적으로 문제를 해결하기는 했으나, 다른 정답자들과 비교하였을 때, 시간 복잡도 측면에서 그렇게 우수한 알고리즘은 아니었던 것 같다..
남들은 O(1)만에 풀었다...ㅠㅠ
뭐 원리는 같았다. 25로 나눈 몫과 나머지를 이용하여 for 문 자체를 돌리지 않고 바로 해당 값을 만족시키는 정수값들을 구한 것이다..
그래도 맞춘걸로 만족해야겠다 다음에는 나도 저런식으로 생각할 수 있겠지ㅎ?

Solution

import sys
input = sys.stdin.readline

if __name__ == "__main__" :
    N , X = map(int, input().strip().split())
    arr = [1]*N
    sum_x = N
    for i in range(N) :
        if X-sum_x == 0 :
            break
        elif X-sum_x < 0 :
            arr = []
            break
        elif X-sum_x <= 25 :
            arr[N-1-i] += X-sum_x
            sum_x += X-sum_x
        elif X-sum_x > 25 :
            arr[N-1-i] += 25
            sum_x += 25
        if i == N-1 and  X > sum_x : 
            arr = []
            break
    if arr :
        string = []
        for num in arr :
            ch = chr(num+64)
            string.append(ch)
    print("".join(string) if arr else "!")