[BOJ/백준] 9519 졸려 파이썬

문제 링크 : https://www.acmicpc.net/problem/9519

9519번: 졸려

 

X가 10억까지여서 규칙을 찾아서 하려고 했던 문제이다.

10번 돌리기에는 너무 많으니까 다시 시작 문자열로 돌아오는 섞는 횟수를 규칙으로 찾으려고 했는데 규칙이 없는 것같아서 포기했다.

 

그래서 그냥 반복문으로 구했다.

다시 시작 문자열로 돌아올때까지 문자를 섞고, 중간에 생성된 문자열을 배열에 추가했다.

예제 1번의 입력이 주어진다면 배열은 아래 순서대로 들어갈 것이다.

acefdb, aedbfc, adfcbe, afbecd, abcdef

 

0번째 다음은 현재에서 한번 깜박였을 때 문자이고 뒤는 한번 깜박이기전 문자이다.

따라서 0번째에서 -X번째가 X번 깜박이기 전 문자열이 된다.

주의 할점은 구해놓은 배열의 크기를 벗어날 수 있으므로 모듈러 연산을 해주자.

 

from sys import stdin

input = stdin.readline

x = int(input())
word = input().strip()
origin = word
word_list = [word]
def solv():
    global x
    cnt = 0
    while True:
        cnt += 1
        mix_word()
        if origin == word:
            break
        word_list.append(word)
    print(word_list[-x%len(word_list)])
def mix_word():
    global word,word_list
    new_word = ''
    mid = len(word)//2
    for idx in range(mid):
        new_word += word[idx]+word[len(word)-1-idx]

    if len(word)%2!=0:
        new_word += word[len(word)//2]

    word = new_word

solv()