Sort - Medium
Given an array of integers arr, sort the array by performing a series of pancake flips.
In one pancake flip we do the following steps:
Choose an integer k where 1 <= k <= arr.length.
Reverse the sub-array arr[0 ~ k-1].
For example, if arr = [3,2,1,4] and we performed a pancake flip choosing k = 3, we reverse the sub-array [3,2,1], so arr = [1,2,3,4] after the pancake flip at k = 3.
Return an array of the k-values corresponding to a sequence of pancake flips that sort arr. Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.
Example 1:
Input: arr = [3,2,4,1]
Output: [4,2,4,3]
Explanation:
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: arr = [3, 2, 4, 1]
After 1st flip (k = 4): arr = [1, 4, 2, 3]
After 2nd flip (k = 2): arr = [4, 1, 2, 3]
After 3rd flip (k = 4): arr = [3, 2, 1, 4]
After 4th flip (k = 3): arr = [1, 2, 3, 4], which is sorted.
Example 2:
Input: arr = [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.
Constraints:
∙ 1 <= arr.length <= 100
∙ 1 <= arr[i] <= arr.length
∙ All integers in arr are unique (i.e. arr is a permutation of the integers from 1 to arr.length).
참고 솔루션
Runtime : 76 ms / Memory : 14.1 MB
class Solution:
def pancakeSort(self, arr: List[int]) -> List[int]:
check = sorted(arr)
if arr == check: # 이미 정렬된 상태면 바로 리턴
return []
n = len(arr)
answer = []
i = n - 1
while i >= 0: # 배열 뒤에서부터 i 인덱스 조회
maxIdx = arr.index(max(arr[0 : i + 1])) # 배열 처음부터 i까지 인덱스 범위 -> 최대값의 인덱스 뽑기
if i != maxIdx: # 현재 루프의 i 인덱스 값이 최대값의 인덱스랑 다를 때
answer.append(maxIdx + 1)
arr[0 : maxIdx + 1] = reversed(arr[0 : maxIdx + 1]) # 최대값의 인덱스까지 포함해서 뒤집기
answer.append(i + 1)
arr[0 : i + 1] = reversed(arr[0 : i + 1]) # 현재 i 번재 인덱스까지 포함해서 뒤집기
i -= 1
return answer 참고
https://programmersought.com/article/4166490926/
https://maxming0.github.io/2020/08/29/Pancake-Sorting/
