[코테 연습] Pancake Sorting
문제
코드를 아래와 같이 작성하긴 했으나, 문제에서 원한게 아니였던 것 같음
1. 가장 큰 숫자를 (fix안된 * fix되었다는것은 자기자리에 있다) 맨앞으로 보냄
2. fix 안된 숫자안에서 reverse함
반복
class Solution:
def listSwap(self,list,idx1,idx2):
list[idx1],list[idx2] = list[idx2],list[idx1]
return list
def pancakeSort(self, A: List[int]) -> List[int]:
res = []
endPoint = len(A)
answer = sorted(A)
while True:
for idx, num in enumerate(A):
if endPoint == 0:
return res
if num == max(A[:endPoint]):
reversePoint = idx
res.append(reversePoint)
A = self.listSwap(A, 0, reversePoint)
A = A[reversePoint+1::-1]
endPoint -= 1
if answer == A:
break
이분 그림 보면 내가한게 맞는데..;; 아니 근데 이 분도 max 선택하고 한걸로 하면 예제랑 들어맞을 수 가 없다.
run하면 답이 다른데 submit하면 답이 맞다니..!? 이게무슨,?!!? 답이 여러개인건가?
class Solution:
def listSwap(self,list,idx1,idx2):
list[idx1],list[idx2] = list[idx2],list[idx1]
return list
def pancakeSort(self, A: List[int]) -> List[int]:
res = []
maxNum = len(A)
answer = sorted(A)
while True:
for idx, num in enumerate(A):
if num == maxNum:
print(maxNum)
reversePoint = idx
A = self.listSwap(A, 0, reversePoint) #가장 큰 값을 맨앞으로 보내줘야함
print(A)
res.append(reversePoint + 1)
print(res)
print("여기서 뒤집:",maxNum-1)
A = A[maxNum-1::-1]
print("뒤집은 결과!:",A)
maxNum -= 1
print("\n")
if maxNum == 1:
break
return res4
[4, 2, 3, 1]
[3]
여기서 뒤집: 3
뒤집은 결과!: [1, 3, 2, 4]
3
[3, 1, 2, 4]
[3, 2]
여기서 뒤집: 2
뒤집은 결과!: [2, 1, 3]
2
[3, 1, 2] << 왜 다시 돌아온거야..?
[3, 2, 3] << 1은 또 어디갔어..?
여기서 뒤집: 1
뒤집은 결과!: [1, 3] << ???????????????
[3, 2, 3]
Process finished with exit code 0
for문 문제인 것같아서 for문 제거하고 while만 돌렸다. 그리고 그냥 maxNum을 len으로만 하니까 저게 문제인가 싶었다.
A: [5, 7, 6, 3, 1, 2, 4]
맨앞으로 보냄: [7, 5, 6, 3, 1, 2, 4]
res: [2]
뒤집은 결과: [4, 2, 1, 3, 6, 5, 7]
A: [4, 2, 1, 3, 6, 5, 7]
맨앞으로 보냄: [6, 2, 1, 3, 4, 5, 7]
res: [2, 5]
뒤집은 결과: [5, 4, 3, 1, 2, 6]
A: [5, 4, 3, 1, 2, 6]
맨앞으로 보냄: [5, 4, 3, 1, 2, 6]
res: [2, 5, 1]
뒤집은 결과: [2, 1, 3, 4, 5]
A: [2, 1, 3, 4, 5]
맨앞으로 보냄: [4, 1, 3, 2, 5]
res: [2, 5, 1, 4]
뒤집은 결과: [2, 3, 1, 4]
A: [2, 3, 1, 4]
맨앞으로 보냄: [3, 2, 1, 4]
res: [2, 5, 1, 4, 2]
뒤집은 결과: [1, 2, 3] << 이제 정렬끝났으니 그만해도돼!!!!!!!!!!!
A: [1, 2, 3]
맨앞으로 보냄: [2, 1, 3]
res: [2, 5, 1, 4, 2, 2]
뒤집은 결과: [1, 2]
[2, 5, 1, 4, 2, 2]
Process finished with exit code 0
대체... 뭐가 문제인걸까.. 분명 정렬이 잘되는데 . .. . . .. ㅠㅠㅠㅠㅠ
class Solution:
def listSwap(self,list,idx1,idx2):
list[idx1],list[idx2] = list[idx2],list[idx1]
return list
def pancakeSort(self, A: List[int]) -> List[int]:
points = []
maxNum = len(A)
answer = sorted(A)
while True:
reversePoint = A.index(maxNum)
A = self.listSwap(A, 0, reversePoint) #가장 큰 값을 맨앞으로 보내줘야함
points.append(reversePoint + 1)
A = A[maxNum-1::-1]+A[maxNum:]
print(A)
maxNum -= 1
if A == answer:
return points[4, 2, 1, 3, 6, 5, 7]
[5, 4, 3, 1, 2, 6, 7]
[2, 1, 3, 4, 5, 6, 7]
[2, 3, 1, 4, 5, 6, 7]
[1, 2, 3, 4, 5, 6, 7]
[2, 5, 1, 4, 2]아,, 정렬할 필요없는 경우에도 답을 return하는구나
[1, 2]
답: [2]class Solution:
def listSwap(self,list,idx1,idx2):
list[idx1],list[idx2] = list[idx2],list[idx1]
return list
def pancakeSort(self, A: List[int]) -> List[int]:
points = []
maxNum = len(A)
answer = sorted(A)
while True:
if A == answer:
return points
reversePoint = A.index(maxNum)
A = self.listSwap(A, 0, reversePoint) #가장 큰 값을 맨앞으로 보내줘야함
points.append(reversePoint + 1)
A = A[maxNum-1::-1]+A[maxNum:]
print(A)
maxNum -= 1
i.e. A is a permutation of the integers from 1 to A.length
분명,, A는 1부터.,,
정렬 잘되는데 ㅠㅠㅠ
[5, 1, 3, 4, 2, 6]
[2, 4, 3, 1, 5, 6]
[1, 3, 2, 4, 5, 6]
[2, 1, 3, 4, 5, 6]
[1, 2, 3, 4, 5, 6]
답: [6, 1, 2, 2, 1]
https://leetcode.com/problems/pancake-sorting/discuss/817862/Python-O(n)-flipsO(n2)-time-explained
[Python] O(n) flips/O(n^2) time, explained - LeetCode Discuss
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
위지원 진짜 도라인가 ㅋㅋㅋㅋㅋㅋㅋ 알고리즘을 이해못한거였음,, 그냥 무작정 index 0 에 가져다 놓는게 아니였음 ㅠㅠ
class Solution:
def pancakeSort(self, A: List[int]) -> List[int]:
points = []
maxNum = len(A)
answer = sorted(A)
while True:
if A == answer:
return points
reversePoint = A.index(maxNum) # 가장 큰 값이 있는 곳을 찾고
points.append(reversePoint + 1)
A = A[reversePoint::-1]+A[reversePoint+1:] # 그 곳에서 뒤집고 안뒤집은건 뒤에 붙여놓고 일단
A = A[maxNum-1::-1]+A[maxNum:] # 다시 그 큰 수를 맨뒤로 보내기 위해 뒤집음
points.append(maxNum)
maxNum -= 1