팬케이크 정렬(Pancake sort)

목차

팬케이크 정렬(Pancake sort)

• 설명
  • 팬케이크 정렬 알고리즘은 무작위로 쌓여있는 팬케이크를 정렬하는 방법이라고 생각하면 됩니다. 뒤집개를 이용해서 제일 꼭대기부터 뒤집개까지를 잡고 뒤집어 가며 정렬하는 것입니다.
  • 같은 말로 0~k까지의 순서를 확 뒤집는 flip을 사용한 정렬방법이라고 할 수 있습니다.
  • 정렬 방법
    • 무작위로 쌓여있는 팬케이크 중에서 가장 큰 팬케이크 찾아 그 펜케이크 밑에 뒤집개를 두고 크게 한번 뒤집습니다. 그러면 제일 큰 팬케이크가 제일 위에 쌓이게 됩니다.
    • 그다음에 이제 전체 팬케이크 탑을 한번 뒤집게 되면 제일 큰 팬케이크가 아래로 오게 됩니다..
    • 다음으로 제일 아래 깔린 팬케이크를 제외하고 그다음으로 큰 팬케이크를 찾고 거기를 기준으로 뒤집개를 두고 뒤집습니다. 그러면 이제 두 번째로 큰 팬케이크가 제일 위에 쌓이게 됩니다. 그다음 마찬가지로 제일 아래 깔린 팬케이크를 제외하고 전체 팬케이크 탑을 한번 뒤집게 되면 두 번째로 큰 팬케이크가 제일 큰 팬케이크 위로 오게 됩니다.
    • 이와 같은 과정을 반복하게 되면 정렬이 완료됩니다..
    • 
• 코드

  • def flip(arr, k):
        arr[: k + 1] = arr[: k + 1][::-1]
        return arr
    
    
    def pancakeSort(arr):
        n = len(arr)
        for curr_size in reversed(range(n)):
            max_index = arr.index(max(arr[: curr_size + 1]))
            if max_index == curr_size:
                continue
            elif max_index == 0:
                arr = flip(arr, curr_size)
            else:
                arr = flip(arr, max_index)
                arr = flip(arr, curr_size)
    
    
    # 예시 배열
    arr = [23, 10, 20, 11, 12, 6, 7]
    pancakeSort(arr)
    print("Sorted Array: ", arr)

• 시간복잡도
  • 모든 요소에 대해(O(n)), 최대값을 찾고 해당 부분에서 뒤집는 과정이 O(n)이므로 총 O(n^2)이 됩니다.

예제

• [백준 2759] 팬케이크 뒤집기
  • 팬케이크 정렬의 대표적인 문제입니다.
  • 위 코드와 동일하게 구현하면 되고, 문제의 요구만 따라주면 손쉽게 해결 가능합니다.

  • import sys
    
    input = sys.stdin.readline
    
    t = int(input())
    
    
    def flip(arr, k):
        arr[: k + 1] = arr[: k + 1][::-1]
        return arr
    
    
    for _ in range(t):
        n, *arr = map(int, input().split())
    
        answer = []
        for curr_size in reversed(range(n)):
            max_index = arr.index(max(arr[: curr_size + 1]))
    
            if max_index == curr_size:  # 이미 아래 있는 상태
                continue
            # 0이면 그게 이미 꼭대기로 온 상태 이미 정렬된경우/ 전체만 뒤집으면 됨
            elif max_index == 0:
                arr = flip(arr, curr_size)
                answer.append(curr_size + 1)
            else:
                arr = flip(arr, max_index)
                answer.append(max_index + 1)
                arr = flip(arr, curr_size)
                answer.append(curr_size + 1)
    
        print(len(answer), *answer)