[ 백준 / G5 / 파이썬 Python ] 9519번 졸려

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

9519번: 졸려

 

코드

---

def solution(x,arr):
    status = int((n := len(arr)) % 2 != 0)
    arr2 = arr.copy()
    cnt = 0
    while 1: # 싸이클 구하기
        left, right = [], []
        for i in range(0, n, 2): left.append(arr2[i])
        for i in range(n - 1 - status, -1, -2): right.append(arr2[i])
        arr2 = left + right
        cnt += 1
        if arr.__eq__(arr2): break

    for k in range(x % cnt): # 정답 구하기
        left, right = [], []
        for i in range(0, n, 2): left.append(arr[i])
        for i in range(n - 1 - status, -1, -2): right.append(arr[i])
        arr = left + right
    return "".join(arr)

print(solution(int(input()),list(input())))

 

풀이

---

이 문제는 정말 쉽게 해결될 것 같지만 몇 가지 장치를 더해줘야 해결할 수 있는 문제였다.

 

문제에 나온 x는 10억이 최대값이기 때문에 x번 반복실행을 통해 해결하려면 시간초과가 발생하게 된다.

따라서 10억번을 진행하지 않기 위해 싸이클을 찾았다.

처음에는 단순하게 홀수, 짝수를 나누어서 싸이클을 구했다. 하지만 생각해보니 어떤 위치에 같은 값들이 존재할지도 모르는 상황에서 단순하게 홀수와 짝수를 나누어서 싸이클을 구할 수가 없었다.

 

따라서 싸이클을 구하는 코드를 작성하였다.

    arr2 = arr.copy()
    cnt = 0
    while 1:
        left, right = [], []
        for i in range(0, n, 2): left.append(arr2[i])
        for i in range(n - 1 - status, -1, -2): right.append(arr2[i])
        arr2 = left + right
        cnt += 1
        if arr.__eq__(arr2): break

위와 같은 코드로 cnt에다 싸이클을 저장하였다.

 

이후에는 위와 똑같은 과정을 거쳐서 정답을 구하고 출력하였다.

   for k in range(x % cnt): # 정답 구하기
        left, right = [], []
        for i in range(0, n, 2): left.append(arr[i])
        for i in range(n - 1 - status, -1, -2): right.append(arr[i])
        arr = left + right
    return "".join(arr)