saurus2
Saurus2
saurus2
전체 방문자
오늘
어제
  • 분류 전체보기
    • 개발
      • AJAX
    • ML Ops
    • Profile
    • 음식점
    • 배낭여행
    • 컴퓨터공학
      • 알고리즘 공부
      • C++
      • Sever 스터디
      • Java spring
      • 알고리즘 _ 문제해결
      • 딥러닝
      • Java 정리
      • Python
      • LeetCode 1000
      • Machine Learning Study
      • Sign language Detection Pro..
      • LeetCode Solutions
    • 비콘
    • 데일리 리포트
    • 유학일기
      • 영어 공부
      • Daily
    • AI Master Degree
      • Data Mining
      • AI and Data engineering
      • Math Foundations for Decisi..
      • Natural Language Processing

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • 백준
  • 릿코드
  • 문제해결능력
  • 온라인저지
  • 개발자 취업준비
  • 딥러닝
  • DFS
  • c++
  • BFS
  • 알고리즘문제해결
  • LeetCode
  • 취업준비
  • 리트코드
  • 취준
  • two pointer
  • 딕셔너리
  • 알고리즘
  • Python
  • 개발자
  • 파이썬

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
saurus2

Saurus2

컴퓨터공학/LeetCode 1000

[LeetCode] 280. Wiggle Sort

2023. 2. 14. 07:20

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]
저작자표시 (새창열림)

'컴퓨터공학 > LeetCode 1000' 카테고리의 다른 글

[LeetCode] 1523. Count Odd Numbers in an Interval Range  (0) 2023.02.14
[LeetCode] 2477. Minimum Fuel Cost to Report to the Capital  (0) 2023.02.12
[LeetCode] 567. Permutation in String  (0) 2023.02.10
[LeetCode] 6. Zigzag Conversion  (1) 2023.02.04
[LeetCode] 1056. Confusing Number  (0) 2023.01.02
    '컴퓨터공학/LeetCode 1000' 카테고리의 다른 글
    • [LeetCode] 1523. Count Odd Numbers in an Interval Range
    • [LeetCode] 2477. Minimum Fuel Cost to Report to the Capital
    • [LeetCode] 567. Permutation in String
    • [LeetCode] 6. Zigzag Conversion
    saurus2
    saurus2
    Simple is Best

    티스토리툴바