[Mock] Uber 1

969. Pancake Sorting

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 arr0...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.

My Answer 1: 아이디어만...

class Solution:
    def pancakeSort(self, arr: List[int]) -> List[int]:
        # 하드 아닌가요...
        ARR = ""
        
        for i in range(len(arr)):
            ARR += str(arr[i])
        
        sarr = ''.join(sorted(ARR))
        
        ans = []
        
        if ARR == sarr:
            return ans

        for i in range(len(ARR)):
            maxi = 0
            for j in range(len(ARR)):
                tmp = ''.join(list(reversed(ARR[:j+1])))
                print(tmp)
                cnt = 0
                if tmp in sarr:
                    if maxi < j+1:
                        maxi = j+1
            print(ARR[:maxi])
            rev = ''.join(list(reversed(arr[:maxi])))
            ARR = rev + ARR[maxi:]
            ans.append(maxi)
        
        return ans

예시로 [1,2] 가 [1,2,3,4] 와 겹치는 부분이 있는지 확인하려면

문자열로 비교해야해서...

우선 arr 을 문자열 형태로 바꿈 => ARR = "3241"
sarr 은 sort 한 형태 => sarr = "1234"

sort 한 것과 원래 값이 같으면 return []

아니면 1 ~ len(arr) 까지 flip 해보면서 많이 겹치는 경우를 찾음
ex) [3,2,4,1]
=> [3,2,4,1], [2,3,4,1], [4,2,3,1], [1,4,2,3]
=> 그래서 [1,4,2,3] 의 1, 2, 3 이 가장 많이 겹치니까 k = 4

라고 생각했는데...

중간에 4가 낑겨있어서 in 으로만 비교해서는 전부 False..

이거 계속 진행했으면 한 4중 for 문은 돌려야했을듯...

그래서 바이루..

Solution 1: Accepted (Runtime: 44 ms - 64.29% / Memory Usage: 14.2 MB - 83.60%)

class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        """ sort like bubble-sort
            sink the largest number to the bottom at each round
        """
        def flip(sublist, k):
            i = 0
            while i < k / 2:
                sublist[i], sublist[k-i-1] = sublist[k-i-1], sublist[i]
                i += 1

        ans = []
        value_to_sort = len(A)
        while value_to_sort > 0:
            # locate the position for the value to sort in this round
            index = A.index(value_to_sort)

            # sink the value_to_sort to the bottom,
            #   with at most two steps of pancake flipping.
            if index != value_to_sort - 1:
                # flip the value to the head if necessary
                if index != 0:
                    ans.append(index+1)
                    flip(A, index+1)
                # now that the value is at the head, flip it to the bottom
                ans.append(value_to_sort)
                flip(A, value_to_sort)

            # move on to the next round
            value_to_sort -= 1

        return ans

여기서 버블 정렬을 쓴다고요...??

근데 result 보니까 더 띠용임

input: [3,2,4,1], expected: [4,2,4,3], output: [3,4,2,3,2]

그래서 확인해보니...
Any valid answer that sorts the array within 10 * arr.length flips will be judged as correct.
라네요...

이런 문제가 다있는...

푸는 방식은

arr is a permutation of the integers from 1 to arr.length
이런 조건이 있기 때문에

value_to_sort = len(A) 로 잡아서 최댓값부터 -1 하는 방식으로...

flip 은 reverse 해주는 역할

ans 에 들어가는 숫자의 의미는 모르겠어요...

Solution 2: Accepted (Runtime: 40 ms - 83.07% / Memory Usage: 14.3 MB - 57.94%)

class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        res = []
        for x in range(len(A), 1, -1):
            i = A.index(x)
            res.extend([i + 1, x])
            A = A[:i:-1] + A[:i]
        return res

더 짧아보여서 가져옴

A 에 A[:i] 까지 reverse 한 것과 원래 A[:i] 합친 것을... 왜지..?

Find the index i of the next maximum number x.
Reverse i + 1 numbers, so that the x will be at A[0]
Reverse x numbers, so that x will be at A[x - 1].
Repeat this process N times.

라는데 이해가 잘 안되네요..^^

---

581. Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order.

Return the shortest such subarray and output its length.

My Answer 1: Accepted (Runtime: 180 ms - 98.73% / Memory Usage: 15.4 MB - 26.83%)

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        snums = sorted(nums)
        idx1 = 0
        idx2 = 0
        
        for i in range(len(nums)):
            if nums[i] != snums[i]:
                idx1 = i
                break
        
        for i in range(len(nums)-1, -1, -1):
            if nums[i] != snums[i]:
                idx2 = i
                break
        
        if idx1 != idx2:
            ans = nums[idx1:idx2+1]
        else:
            ans = []
        
        return len(ans)

정렬된 nums 인 snums 와 비교해서

가장 먼저 제자리에 없는 값의 인덱스를 idx1 으로, (왼쪽부터)

가장 마지막으로 제자리에 없는 값의 인덱스를 idx2 로 잡고 (오른쪽부터 - reverse)

idx1 과 idx2 가 같으면 모두 정렬됐다는 것이므로 ans = []

다르면 idx1 ~ idx2 까지 슬라이싱 => ans = nums[idx1:idx2+1]