[코테 연습] Pancake Sorting

문제

https://leetcode.com/explore/challenge/card/august-leetcoding-challenge/553/week-5-august-29th-august-31st/3441/

 

---

 

 

코드를 아래와 같이 작성하긴 했으나, 문제에서 원한게 아니였던 것 같음

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

 

https://leetcode.com/problems/pancake-sorting/discuss/818239/Simple-image-for-intuition-without-code-solution.

 

이분 그림 보면 내가한게 맞는데..;; 아니 근데 이 분도 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 res

4
[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

제발... ACCCCCCPPPPEEENNNTTAAANNNCCCEE!!!!!!해주세요!!

 

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

 

 

위지원 진짜 도라인가 ㅋㅋㅋㅋㅋㅋㅋ 알고리즘을 이해못한거였음,, 그냥 무작정 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