https://leetcode.com/problems/pancake-sorting/description/
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] (0-indexed).
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).
처음 접하는 유형의 문제다.
Sorting을 겁나 하는 그런 문제;;
1. Python
좀 비효율적이긴 하지만, 아래와 같이 풀었다.
분명 문제가 없어 보이는데, Test case에서 fail이 난다.
근데 진짜 문제는, test case fail이 난 것을 보아도 뭐가 문제인지 모르겠다.. Test case가 의심갈 지경임
class Solution:
def pancakeSort(self, arr: List[int]) -> List[int]:
ans = []
arr2 = sorted(arr)
n = len(arr)
while arr!=arr2 :
if arr[:n].index(max(arr[:n])) == n-1 :
n -= 1
arr = arr[:n]
arr2 = sorted(arr)
continue
else:
idx = arr[:n].index(max(arr[:n]))
ans.append(idx+1)
temp = arr[:idx+1]
temp.reverse()
arr = temp + arr[idx+1:]
ans.append(n)
arr.reverse()
n -= 1
arr2 = sorted(arr)
return ans
아.. 계속 코드를 째려보다보니 while 안에 else 부분에서 if와 같이 arr를 잘라내서 update했어야 한다.
겁나리 비효율적인 코드긴 한데 뭐.. 코드 돌아가면 됐지 ㅋ
GPT한테도 코드 비효율적이라고 혼나긴했다.
수정 코드는 아래와 같다.
from typing import List
class Solution:
def pancakeSort(self, arr: List[int]) -> List[int]:
ans = []
arr2 = sorted(arr)
n = len(arr)
while arr!=arr2 :
if arr[:n].index(max(arr[:n])) == n-1 :
n -= 1
arr = arr[:n]
arr2 = sorted(arr)
continue
else:
idx = arr[:n].index(max(arr[:n]))
ans.append(idx+1)
temp = arr[:idx+1]
temp.reverse()
arr = temp + arr[idx+1:]
ans.append(n)
arr.reverse()
n -= 1
arr = arr[:n]
arr2 = sorted(arr)
return ans
근데, 각종 풀이법을 찾아봤는데 메카니즘은 내 풀이와 유사하다.
단지 어떻게 그걸 좀 더 Fency하고 Efficient하게 표현했냐의 차이..!
"""
나와 비슷한 풀이
class Solution:
def pancakeSort(self, arr: List[int]) -> List[int]:
res=[]
for i in range(len(arr)-1,-1,-1):
if arr[i]!=i+1:
for j in range(i-1,-1,-1):
if arr[j]==i+1:
break
arr[:j+1]=arr[:j+1][::-1]
arr[:i+1]=arr[:i+1][::-1]
res.append(j+1)
res.append(i+1)
return res
"""
"""
GPT 풀이
이것도 나와 유사하다
class Solution:
def pancakeSort(self, arr: List[int]) -> List[int]:
ans = []
n = len(arr)
while n > 1:
# 현재 배열에서 최대값의 인덱스 찾기
max_idx = arr.index(max(arr[:n]))
# 최대값이 이미 올바른 위치에 있는 경우
if max_idx == n - 1:
n -= 1
continue
# 최대값을 배열 맨 앞으로 이동
if max_idx != 0:
ans.append(max_idx + 1)
arr[:max_idx + 1] = reversed(arr[:max_idx + 1])
# 최대값을 배열 맨 뒤로 이동
ans.append(n)
arr[:n] = reversed(arr[:n])
# 유효한 범위를 줄임
n -= 1
return ans
"""
C++ Vector로도 한 번 풀어보자.
2. C++
요점은, C++에서도 Python의 MAX처럼 "algorithm" header 안에 max_element라는 method가 있고 이 놈은 해당 max value의 iterator를 반환하므로, 이걸 index화 시키기 위해선 또 distance 라는 method를 써줘야 한다.
그리고, max_element, sortted, reverse 와 같이 container의 begin, end를 받는 method의 경우 뒤쪽 end쪽에 있는 녀석에 항상 +1을 해줘서 넉넉히 searching 한다고 생각해야 한다.
뭔가 index 적으론 항상 size에 -1을 해줘야 하지만, 위 begin/end의 경우엔 그냥 size를 생짜로 집어 넣는다고 생각하자.
class Solution {
public:
vector<int> pancakeSort(vector<int>& arr) {
int n = arr.size();
vector<int> ans;
while(n>1){
auto max_it = max_element(arr.begin(),arr.begin()+n);
int dist = distance(arr.begin(),max_it);
if(dist == n-1){
n--;
continue;
}
if(dist!=0){
ans.push_back(dist+1);
reverse(arr.begin(),arr.begin()+dist+1); // kick point, 이런식으로 begin,end 쓸 때는 항상 뒤에 범위에 하나 더 +1 한다고 생각하자.
}
ans.push_back(n);
reverse(arr.begin(),arr.begin()+n);
n--;
}
return ans;
}
};