-
94일 (75. Sort Colors) two pointers, quickSort지식/알고리즘 2023. 12. 23. 16:29
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 세개이므로 완전한 정렬 알고리즘을 구현하여 사용하는 것보다
투 포인터와 퀵소트의 원리를 이용하여 접근하였다.
(논리적으로 공간을 구분지으며 스왑하는 형식으로 접근하는 게 완전한 정렬알고리즘보다 공간복잡도에 이점이 있다.)
0. 배열 nums에 주어지는 원소는 3종류이므로 ptr1은 0을 가르키는 인덱스, ptr2는 1을 가르키는 인덱스, 그 외의 값인 2는 배열의 끝자락으로 넣었다. (포인터의 위치는 nums[ptr1+1] == 1, nums[ptr2+1] == 2 이다.)
1. 현재 ptr2가 가르키는 값이 0이라면?
현재 ptr2의 값과 현재 ptr1의 값을 스왑한 후 ptr1은 다음 인덱스를 가르킨다.(ptr1++)
ptr1이 다음 인덱스를 가르킨다면 자연히 ptr2의 논리적 공간도 1칸 밀려나기때문에 다음 인덱스를 가르켜야한다.
2. 현재 ptr2가 가르키는 값이 1이라면?
ptr1의 공간은 그대로이며, ptr2의 논리적인 공간이 하나 늘어나므로 ptr2는 ptr2++를 가르킨다.
3. 현재 ptr2가 2를 가르킨다면? 배열의 끝자락 인덱스와 현재 ptr2 인덱스의 값을 스왑한다.
배열의 끝자락의 숫자는 2이므로 더 이상 볼 필요가 없으므로 논리적으로 제외하기위해 n-- 을 한다.(n = array.length-1)
- 코드
class Solution { public void sortColors(int[] nums) { int ptr1 = 0; int ptr2 = 0; int n = nums.length-1; while(ptr2 <= n) { if(nums[ptr2] == 0) swap(nums, ptr1++, ptr2++); // 1 else if(nums[ptr2] == 1) ptr2++; // 2 else swap(nums, ptr2, n--); // 3 } } private void swap(int[] array, int firstIdx, int secondIdx) { int tmp = array[firstIdx]; array[firstIdx] = array[secondIdx]; array[secondIdx] = tmp; } }
실제로 공간을 구분짓는 것이 아닌 포인터로 현재 공간의 위치를 가르키면서
논리적으로 공간을 구분짓는 것이 포인트이다.
https://leetcode.com/problems/sort-colors/
Sort Colors - LeetCode
Can you solve this real interview question? Sort Colors - Given an array nums with n objects colored red, white, or blue, sort them in-place [https://en.wikipedia.org/wiki/In-place_algorithm] so that objects of the same color are adjacent, with the colors
leetcode.com
'지식 > 알고리즘' 카테고리의 다른 글
96일 (2161. Partition Array According to Given Pivot) pointer (0) 2023.12.25 95일 (2149. Rearrange Array Elements by Sign) pointers (0) 2023.12.24 93일 (1721. Swapping Nodes in a Linked List) pointers (0) 2023.12.22 92일 (2396. Strictly Palindromic Number) Two pointers, String (0) 2023.12.21 91일 (202. Happy Number) two poniters (0) 2023.12.20