https://leetcode.com/problems/sort-colors/
코드설명
삽입정렬(Insertion Sort) + 합병정렬(Merge Sort) + 퀵정렬(Quick Sort) 을 활용합니다.
사실, 여기서 위의 3가지 정렬방식중 2가지만 In-Place 정렬입니다.
삽입정렬(Insertion Sort)과 퀵정렬(Quick Sort)입니다.
>>
합병정렬(Merge Sort)는 In-Place 정렬이 아닌, 별도의 메모리를 활용합니다.
위의 3가지 방식을 활용하여 구현해보겠습니다.
코드
1. 선택정렬(Selection Sort) 시간복잡도 O(N^2) 공간복잡도 O(1)
가장 앞에서부터 처리하며, 나머지 범위 중 가장 작은 값을 "선택Selection"을 하여 가장 작은 숫자씩 하나씩 선택한다는 의미에서 선택정렬입니다.
class Solution { public void sortColors(int[] nums) { int N = nums.length; for(int i=0; i<N; i++){ int minIdx = i; for(int j=i+1; j<N; j++){ if(nums[minIdx] > nums[j]){ minIdx = j; } } swap(nums, minIdx, i); } } void swap(int[] nums, int a, int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }
2. 삽입정렬(Insertion Sort) 시간복잡도 빅오 O(N^2) 빅오메가 O(N), 공간복잡도 O(1) In-Place이기에 공간복잡도는 O(1)입니다.
앞에서부터 한개의 공간씩 값을 확정시킵니다. 만약, i-1이 < i 인 상황이라면, [0..i-1]번에서는 반드시 정렬되어 있음이 보장됩니다.
class Solution { public void sortColors(int[] nums) { int N = nums.length; for(int i=0; i<N; i++){ int j = i; while(j > 0 && nums[j-1] > nums[j]){ swap(nums, j-1, j); j -= 1; } } } void swap(int[] nums, int a, int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }
3. 합병정렬(merge sort)를 활용한 경우입니다. 공간복잡도 O(N), 시간복잡도 O(n log n)
문제에서 nums[]값이 In-Place Sort가 아니기에 값이 바뀌어서 이 문제를 통과하지 못합니다.
class Solution { public void sortColors(int[] nums) { nums = mergeSort(nums, 0, nums.length - 1); } int[] mergeSort(int[] nums, int left, int right){ if(left == right){ return new int[]{nums[left]}; } int mid = (left + right) / 2; int[] l = mergeSort(nums, left, mid); int[] r = mergeSort(nums, mid + 1, right); int[] sorted = merge(l, r); return sorted; } int[] merge(int[] l, int[] r){ int[] arr = new int[l.length + r.length]; int left = 0, right = 0; int idx = 0; while(left < l.length && right < r.length){ if(l[left] < r[right] ){ arr[idx++] = l[left++]; } else if(l[left] >= r[right] ){ arr[idx++] = r[right++]; } } while(left < l.length){ arr[idx++] = l[left++]; } while(right < r.length){ arr[idx++] = r[right++]; } return arr; } }
4. 퀵정렬(QuickSort) 사용한경우. 시간복잡도 O(n log n) 공간복잡도 O(1) -> 재귀 메모리스택은 제외하고 생각.
class Solution { public void sortColors(int[] nums) { int N = nums.length; quickSort(nums, 0, N - 1); } void quickSort(int[] A, int start, int end){ if(start >= end) return ; int partitionIdx = partition(A, start, end); quickSort(A, start, partitionIdx - 1); quickSort(A, partitionIdx + 1, end); } int partition(int[] A, int start, int end){ int pivot = A[start]; int left = start + 1; int right = end; while(left <= right){ while(left <= end && pivot >= A[left]){ left ++; } while(right >= start && pivot < A[right]){ right--; } if(left < right){ swap(A, left, right); } } swap(A, start, right); return right; } void swap(int[] nums, int a, int b){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } }
4. HashMap을 활용한경우입니다.
class Solution { public void sortColors(int[] nums) { HashMap<Integer, Integer> hashmap = new HashMap<>(); for(int i=0; i<nums.length; i++){ hashmap.put(nums[i], hashmap.getOrDefault(nums[i], 0) + 1); } int idx = 0; for(int i=0; i<3; i++){ if(hashmap.containsKey(i)){ int frequency = hashmap.get(i); for(int j=0; j<frequency; j++){ nums[idx++] = i; } } } } }
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode] 48. Rotate Image - 구현(Implementation) JAVA (0) | 2024.12.01 |
---|---|
[LeetCode] 54. Spiral Matrix - 구현(Implementation) JAVA (0) | 2024.12.01 |
[LeetCode] 56. Merge Intervals - 구현(Implementation) JAVA (0) | 2024.11.28 |
[LeetCode] 47. Permutations II - 깊이우선탐색(DFS) + 해시셋(HashSet) + 비트마스크(BitMask) JAVA (0) | 2024.11.28 |
[LeetCode] 40. Combination Sum II - 깊이우선탐색(DFS) + 해시셋(HashSet) JAVA (0) | 2024.11.28 |