난이도

Gold 5

인증

문제

선영이는 다가오는 COCI에 사용할 데이터를 만드느라 삼일동안 깨어있었다. 더 이상 데이터를 만들 수 없는 상황에 이르렀고, 심지어 선영이는 신경쇠약에 걸려 아무것도 제대로 보지 못하는 상황이 되었다.

선영이가 무엇인가를 읽다가 눈을 한 번 깜박하면 단어의 뒷 부분 절반이 앞 부분과 섞이게 된다. (길이가 홀수인 경우에는 뒷 부분의 길이가 짧다) 섞이는 방법은 아래와 같다.

마지막 글자가 첫 번째 글자와 두 번째 글자 사이로 이동한다. 뒤에서 두 번째 글자가 두 번째 글자와 세 번째 글자 사이로 이동한다. 뒤에서 k번째 글자는 앞에서부터 k번째와 k+1번째 글자 사이로 이동한다. 예를 들어, 선영이가 “abcdef”란 단어를 보다가 눈을 한 번 깜박이면, 단어가 “afbecd”가 된다. 여기서 한 번 더 깜박이면 “adfcbe”가 된다.

선영이는 한 단어를 쓰고난 이후에 눈을 X번 깜박였고, 처음에 작성한 단어가 무엇인지 궁금해졌다. X와 눈을 X번 깜박인 후에 선영이가 보고 있는 단어가 주어졌을 때, 원래 단어가 무엇이었는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 X(1 ≤ X ≤ 1,000,000,000) 가 주어지고, 둘째 줄에 X번 깜박인 후의 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 구간 [3,1000]에 포함된다.

출력

첫째 줄에 X번 깜박이기 전 단어를 출력한다.

예제 입력

4
acefdb

예제 출력

abcdef

해설 및 후기

트릭을 사용하기보다는 구현에 가깝게 풀었다. pop과 같은 연산이 걱정이었지만 문자열의 길이가 최대 1000이라 시간 내에 충분히 작동할 것이라고 생각이 들었고, 한번 깜빡일 때의 동작을 구현해 n번 내에 동일한 문자열이 등장한다면 주기가 발생한 것으로 간주해 즉시 답을 구하고, 그렇지 않다면 n번 순회하면서 원래 단어를 구한다.

제출 코드

n = int(input())
w = list(input())
sz = len(w) // 2
def rBlink(l):
    tmp = []
    tmpList = l[:]
    for i in range(sz):
        tmp.append(tmpList.pop(i+1))
    for i in list(reversed(tmp)):
        tmpList.append(i)
    return tmpList

cList = w[:]
i = 0
while(i < n):
    cList = rBlink(cList)
    i += 1
    if(cList == w):
        break #이제 i는 주기

for j in range(n%i):
    cList = rBlink(cList)

for i in cList:
    print(i, end='')
print()