[LeetCode] 280. Wiggle Sort

280. Wiggle Sort

Medium

Given an integer array nums, reorder it such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

You may assume the input array always has a valid answer.

 

Example 1:

Input: nums = [3,5,2,1,6,4]
Output: [3,5,1,6,2,4]
Explanation: [1,6,2,5,3,4] is also accepted.

Example 2:

Input: nums = [6,6,5,6,3,8]
Output: [6,6,5,6,3,8]

 

Constraints:

• 1 <= nums.length <= 5 * 104
• 0 <= nums[i] <= 104
• It is guaranteed that there will be an answer for the given input nums.

 

Follow up: Could you solve the problem in O(n) time complexity?

---

문제 풀이

주어진 배열을 지그재그로 정렬해야한다.

첫번째 숫자는 두번째 숫자보다 작거나 같고, 두번째 숫자는 새번째 숫자보다 크거나 같아야한다.

네번째 다섯번째 숫자도 마찬가지로 지그재그로 크기가 달라야한다.

시간복잡도를 정할때 문제 제한을 보면 최대 값이 5 * 10^4 이기 때문에 O(N^2)으로 풀기에는 조금 버거워 보이기도 한다. 

정렬 O(NlogN)

숫자 배열을 우선 정렬하고 2칸씩 옮기면서 지금 자리보다 1개 앞인 자리의 숫자를 교환한다. 

배열을 정렬했기 때문에 뒤로 갈수록 숫자가 커지는건 보장이 되기 때문에 2개씩 숫자를 교환해주면 

그 두자리의 수들은 지그재그 정렬 조건에 맞아 떨어진다. 

그리고 그 다음 숫자는 정렬한 배열에서는 앞 숫자들보다 클 수 밖에 없다. 

그리디 O(N)

자리 수가 짝수이면서 앞자리가 그 다음자리 숫자보다 큰 경우

자리 수가 홀수이면서 앞자리가 그 다음자리 숫자보다 작은 경우

위 두가지 조건에 두자리 수를 교환한다. 

짝수 자리의 경우 뒷자리 숫자가 무조건 크거나 같아야하고, 홀수 자리의 경우 뒷자리 숫자가 무조건 작거나 같아야한다.

이런 조건을 맞춰 숫자를 교환하다보면 숫자가 하나씩 밀리면서 위 조건들을 만족하도록 배열을 바꾸게 된다. 

소스 코드

정렬

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()
        for i in range(1, len(nums) - 1, 2):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]

그리디

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for i in range(len(nums) - 1):
            if i % 2 == 0 and nums[i] > nums[i + 1] \
            or i % 2 == 1 and nums[i] < nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]