백준 9519번 - 졸려(Python)

문제

https://www.acmicpc.net/problem/9519

9519번: 졸려

풀이

처음으로 생각해 낸 방법은 문제에 나와있는 셔플을 그대로 역으로 실행하는 것을 n만큼 반복하는 반복하는 것이었는데, 문제를 잘 보니 n 크기가 최대 10억이었다(...).
보통 이렇게 무언가를 반복해야 하는 문제인데 n값이 터무니없이 크다면 주기가 있는 경우가 많아서, 일단 문제에 나와있는 대로 코드를 짠 다음 주기를 찾아보려고 했다.
4~10글자로 셔플을 돌려보니 주기가 있는 것은 확실한데, 그 주기가 글자 길이와는 관련이 없어보였다. 그래서 직접 주기를 구해야 했는데, 200글자짜리 단어를 넣었을 때 주기가 171인 것을 보고 길이가 1000이어도 주기는 2000을 넘지 않겠다 싶어서 최대 반복 횟수는 2000으로 정했다.
위의 반복문에서 주기를 찾은 후에는, 원래 값에서 n(n < 주기)번 깜빡여서 입력받은 단어가 되었다면, 입력받은 단어에서 (주기 - n)번 더 깜빡이면 원래 값으로 되돌아간다는 점을 이용하여 정답을 구했다.

나의 코드

n = int(input())
string = input()
half = len(string) // 2 + (len(string) & 1)
str1 = list(string[:half])
str2 = list(string[half:])
cnt = 0

for i in range(2000):
    idx = len(string) // 2 - 1
    j = 1
    while idx >= 0:
        str1.insert(j, str2[idx])
        idx -= 1
        j += 2
    str2 = str1[half:]
    str1 = str1[:half]
    cnt += 1
    if (str1 + str2 == list(string)):
        break

period = cnt - n % cnt

for i in range(period):
    idx = len(string) // 2 - 1
    j = 1
    while idx >= 0:
        str1.insert(j, str2[idx])
        idx -= 1
        j += 2
    str2 = str1[half:]
    str1 = str1[:half]

print(''.join(str1 + str2))

첫번째 반복문이 주기를 찾는 반복문이고, 두번째 반복문이 정답을 찾는 반복문이다.
period = cnt - n % cnt는 n번 깜빡이기 전으로 돌아가는 것 == (주기-n)번만큼 더 깜빡이는 것을 이용해서 앞으로 몇 번 더 깜빡여야 할 지를 계산한 부분이다.