[LeetCode] 75. Sort Colors

문제 출처: https://leetcode.com/problems/sort-colors/

Sort Colors - LeetCode

---

문제

빨강, 하양 그리고 파란색으로 칠해진 n개의 객체 배열 nums가 주어진다. 같은 색이 인접하도록 내부 정렬하여라.

 

빨강, 하양 그리고 파랑을 정수 0, 1 그리고 2로 대체한다.

 

문제를 풀 때 내부 라이브러리의 정렬을 사용하지 마라.

예제

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

풀이

전형적인 정렬 문제이다.

 

퀵 정렬을 이용하여 문제를 풀었으며, 코드는 다음과 같다.

var sortColors(nums) {
	quickSort(nums, 0, nums.length-1);
}

function quickSort(nums, left, right) {
	const index = partition(nums, left, right);
    if (left < index-1) {
    	quickSort(nums, left, index-1);
    }
    if (index < rihgt) {
    	quickSort(nums, index, right);
    }
}

function partition(nums, left, right) {
	const pivot = nums[left + Math.floor((right-left)/2)];
    
    while (left <= right) {
    	while (pivot > arr[left]) { left += 1; }
        while (pivot < arr[right]) { right -= 1; }
    	
        if (left <= right) {
        	[nums[left], nums[right]] = [nums[right], nums[left]];
            left += 1;
            right -= 1;
        }
    }
    
    return left;
}

시간 복잡도는 퀵 정렬의 시간 복잡도를 따르며, 평균 $O(nlogn)$의 복잡도를 갖고, 최악의 경우$(n^2)$이 된다.

 

Github: 75.js

GitHub - opwe37/Algorithm-Study