[ BOJ ] 2759 : 팬케이크 뒤집기 ( GOLD 4 ) / Python

문제

서로 다른 크기의 n개의 팬케이크가 쌓여 있다. 순서 없이 마구 쌓여져있는 팬케이크를 크기 순대로 쌓으려고 한다. 가장 위에는 제일 작은 크기의 팬케이크가 있어야 되고, 가장 아래에는 제일 큰 크기의 팬케이크가 있어야 한다.

팬케이크를 뒤집는 방법은 위에서 k개의 순서를 뒤집는 것이다. 따라서 k번째 팬케이크가 가장 위로 올라오게 되고, 제일 위에 있던 팬케이크는 k번째가 된다.

다음 예를 보자.

팬케이크가 쌓여있는 상태가 주어졌을 때, 이를 순서대로 만드는 방법을 찾아 출력하는 프로그램을 작성하시오. 팬케이크는 최대 max(0, 2n-3)번 뒤집을 수 있다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 숫자 여러개가 공백으로 구분되어있다. 첫 번째 숫자는 팬케이크의 개수 N이고, 그 다음 N개의 숫자는 팬케이크의 크기이다. 가장 위에 있는 팬케이크가 첫 숫자이고, 마지막 숫자는 제일 아래에 있는 팬케이크이다.  N은 30보다 작거나 같다. 팬케이크의 크기는 서로 다르며, 1보다 크거나 같고, N보다 작거나 같다.

출력

각 테스트 케이스에 대해 한 줄에 하나씩 뒤집는 방법을 출력한다. 제일 먼저 뒤집는 횟수 K를 출력한다. 그 다음 뒤집는 방법을 순서대로 출력하면 된다. 뒤집는 방법이 여러개일 때는, 아무거나 출력하면 된다.

풀이 과정

뒤집는 방법이 여러개일 때는 아무거나 출력하면 되므로, 원하는 대로 팬케이크를 뒤집어도 무방하다!

해당 풀이 과정에 대한 아이디어는 하노이 탑과 비슷하다고 생각하여 얻게 되었다.

가장 큰 팬케이크를 먼저 배치하자는 생각을 중점으로 다음과 같이 풀이가 가능하다.

 

제일 큰 팬케이크 숫자부터 차례대로 맨 밑으로 보내야 한다. 그래야 차곡차곡 크기 순서대로 팬케이크를 쌓을 수 있다.

팬케이크를 맨 밑으로 보내는 과정은 다음과 같다. 예시를 위해 4 5 1 3 2 가 입력으로 들어왔다고 가정한다.

 

1.가장 큰 팬케이크의 위치를 찾아 맨 위부터 가장 큰 팬케이크의 위치까지 뒤집는다. ( 만약 이미 맨 위에 가장 큰 팬케이크가 있다면 넘어간다. ) 이렇게 뒤집으면 맨 위에 가장 큰 팬케이크가 오게 된다.

2. 맨 위에 온 가장 큰 팬케이크부터 그 팬케이크를 넣고 싶은 위치까지 뒤집어 원하는 위치에 팬케이크를 둔다. 이 팬케이크는 위치를 잘 찾아 가게 된다.

3. 배치를 완료한 팬케이크를 제외하고, 가장 큰 팬케이크를 찾아 뒤집어서 위로 올리고 (1번) / 맨 위부터 원하는 위치까지 뒤집어서 원하는 위치로 배치하기 (2번)을 반복한다.

 

( 이 과정은, 찾고 있는 큰 팬케이크가 이미 맨 밑에 배치되어 있는 상태이기 때문에 스킵해도 된다. )

다음을 반복하면 팬케이크 뒤집기 순서를 얻을 수 있다.

만약 팬케이크를 뒤집는 도중 이미 정렬이 되어있다면 종료할 수 있다.

 

만약 찾는 가장 큰 팬케이크가 이미 맨 위에 있다면, 바로 원하는 위치에 뒤집으면 된다.

 

이 과정을 반복하면서 뒤집은 팬케이크 갯수를 저장한 뒤, 이를 출력해주면 되는 문제이다. 특정 팬케이크를 원하는 위치에 배치하고 싶다면 맨 위로 올려야하는 것이 키포인트 아이디어이다.

import sys
input = sys.stdin.readline

t = int(input().rstrip())
for _ in range(t):
    n, *arr = list(map(int, input().rstrip().split()))
    now = n
    result = []
    while now != 1 and arr != sorted(arr):
        if arr[0] != now:
            result.append(arr.index(now) + 1)
            arr = arr[:arr.index(now)+1][::-1] + arr[arr.index(now)+1:now] + arr[now:]
        result.append(now)
        arr = arr[:now][::-1] + arr[now:]
        now -= 1
    
    print(len(result), ' '.join(map(str, result)))