[LeetCode] - 75. Sort Colors

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '중간 (Medium)' 단계인 "Sort Colors" 문제입니다.

--> https://leetcode.com/problems/sort-colors/description/

 

문제 :

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library's sort function.

---

Example 1:

Input: nums = [2,0,2,1,1,0]

Output: [0,0,1,1,2,2]

 

Example 2 :

Input : nums = [2,0,1]

Output: [0,1,2]

 

Constraints :

• n == nums.length
• 1 <= n <= 300 nums[i] is either 0, 1, or 2.

Follow up : Could you come up with a one-pass algorithm using only constant extra space?

---

이 문제는 주어진 배열에서 0, 1, 2로 표현된 빨강, 흰색, 파랑 색상 객체들을 정렬하는 문제입니다.

정렬 결과는 같은 색상끼리 인접하게 배치되고, 빨강, 흰색, 파랑 순서로 배열되어야 합니다. 추가적인 정렬 함수 없이 제자리에서 정렬해야 하며, 상수 공간 복잡도로 한 번의 순회로 해결해야 합니다.

 

1. 삽입정렬 코드 : 

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int key = 0;
        for (int i = 1; i < n; i++) {
            key = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > key) {
                nums[j+1] = nums[j];
                j = j - 1;
            }
            nums[j+1] = key;
        }
    }
}

1

 

 

이 코드는 삽입 정렬(Insertion Sort)을 사용하여 주어진 배열을 정렬합니다. 삽입 정렬은 배열을 순회하면서 정렬되지 않은 부분에서 요소를 하나씩 꺼내어 정렬된 부분에 삽입하는 방식입니다.

1. 초기화:
   • 배열의 길이를 변수 n에 저장합니다.
   • 정렬할 요소를 저장할 key 변수를 선언합니다.
2. 삽입 정렬 알고리즘:
   • 배열의 두 번째 요소부터 시작하여 순회합니다.
   • key 변수에 현재 요소를 저장합니다.
   • while 루프를 통해 key보다 큰 요소를 오른쪽으로 이동시킵니다.
   • key를 올바른 위치에 삽입합니다.

시간 및 공간 복잡도:

1. 시간 복잡도:
   • 삽입 정렬의 최악 시간 복잡도는 O(n^2)입니다. 이는 각 요소에 대해 삽입 위치를 찾기 위해 최대 n번 비교 및 이동이 필요하기 때문입니다.
   • 최선의 경우(이미 정렬된 배열)에는 O(n)입니다.
2. 공간 복잡도:
   • 삽입 정렬은 제자리 정렬 알고리즘이므로 추가적인 배열이나 리스트를 사용하지 않습니다. 따라서 공간 복잡도는 O(1)입니다.

결론:

이 코드는 삽입 정렬을 사용하여 배열을 정렬합니다. 하지만 주어진 문제를 해결하는 데는 최적의 방법이 아닙니다. 문제에서 요구하는 시간 복잡도 O(n)과 공간 복잡도 O(1)을 만족하지 않습니다.

 

그래서 One-pass로 하려면, 네덜란드 국기 문제 알고리즘(Dutch National Flag Problem)을 사용해야 합니다.

---

2. 네덜란드 국기 알고리즘 : 

class Solution {
    public void sortColors(int[] nums) {
        int low = 0, mid = 0, high = nums.length - 1;

        while (mid <= high) {
            if (nums[mid] == 0) {
                swap(nums, low, mid);
                low++;
                mid++;
            } else if (nums[mid] == 1) {
                mid++;
            } else {
                swap(nums, mid, high);
                high--;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

 

1. 포인터 초기화:
   • low는 0의 위치를 추적합니다.
   • mid는 현재 요소를 검사하는 위치입니다.
   • high는 2의 위치를 추적합니다.
2. 세 가지 경우 처리:
   • nums[mid]가 0이면, low와 mid를 교환하고 low와 mid를 증가시킵니다.
   • nums[mid]가 1이면, mid만 증가시킵니다.
   • nums[mid]가 2이면, mid와 high를 교환하고 high를 감소시킵니다.
3. 교환 함수:
   • nums 배열에서 두 요소의 위치를 교환합니다.

시간 및 공간 복잡도:

• 시간 복잡도: O(n)
  • 배열을 한 번 순회하면서 정렬하므로 시간 복잡도는 O(n)입니다.
• 공간 복잡도: O(1)
  • 추가적인 배열이나 리스트를 사용하지 않고, 상수 공간만 사용하므로 공간 복잡도는 O(1)입니다.

그래서 이 코드가 아마 문제가 원했던 풀이가 아닐까 싶습니다.

---

삽입정렬, 네덜란드 국기 Runtime 결