969. Pancake Sorting

https://leetcode.com/problems/pancake-sorting/

Pancake Sorting - LeetCode

 

기본 아이디어

 

1. 가장 max 값을 찾는다.

2. max 값을 top으로 보내기 위해 뒤집는다.

3. max 값을 bottom으로 보내기 위해 뒤집는다.

4. 정렬되지 않은 배열의 길이가 감소(-1)한다.

 

위의 4가지 방법을 다시 순차적으로 진행한다.

 

class Solution(object):
    def pancakeSort(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        
        last_pos = len(A) - 1
        #print(A)
        results = []
        
        while last_pos > 0:
            max_element_idx = A.index(max(A[:last_pos+1]))
                                  
            #print(max_element_idx+1,"MAX")

            if max_element_idx != last_pos:

                A = A[:max_element_idx+1][::-1] + A[max_element_idx+1:]
                print(A)
                results.append(max_element_idx+1)

                A = A[:last_pos+1][::-1] + A[last_pos+1:]
                print(A,"AFTER")
                results.append(last_pos+1)
            last_pos-=1
        return results