[LeetCode#75] Sort Colors

 

❒ Description

---

날짜	2024.09.30 (월)
레벨	Medium
제목	Sort Colors
링크	https://leetcode.com/problems/sort-colors/description/?envType=problem-list-v2&envId=sorting
알고리즘	Dutch National Flag, Insertion-sort
시간 복잡도	O(N)

 

 

 

 

 

❒ 문제 및 로직 분석

---

이번 문제는 in-place 알고리즘을 사용해서 풀이해야 하는데, 그 중에서는 시간복잡도가 O(N)인 

네덜란드 국기 (Dutch National Flag) 알고리즘을 구현해야 하는 문제이다. 물론 삽입 정렬로도

풀이가 가능하지만 삽입정렬은 input의 크기가 커질수록 성능이 저하되기 때문에 여기서는 제외다.

 

 

 

 

 

❒ Solution

---

1. 삽입 정렬

public void sortColors(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int target = nums[i];
        int beforeIdx = i - 1;
        while (beforeIdx >=0 && nums[beforeIdx] > target) {
            nums[beforeIdx + 1] = nums[beforeIdx];
            nums[beforeIdx] = target;
            beforeIdx --;
        }
    }
}

 

 

2. DNF 알고리즘

public void sortColors(int[] nums) {
    int low = 0;
    int mid = 0;
    int high = nums.length - 1;
    
    while (mid <= high) {
      if (nums[mid] == 2) {
          swap(nums, mid, high);
          high --;
      } else if (nums[mid] == 1) {
          mid ++;
      } else if (nums[mid] == 0) {
          swap(nusm, low, mid);
          low ++;
          mid ++;
      }
    }
}

private void swap(int[] nums, int v1, int v2) {
    int tempt = nums[v2];
    nums[v2] = nums[v1];
    nums[v1] = temp;
}

 

 

 

 

 

 

---