.leetcode(75. Sort Colors)

문제

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

문제 풀기 전

1. quick sort로 풀라는 걸로 들렸다.
2. Lumoto방법만 알고 있었는데 hoare방법으론 안풀었는데 중복이기에 hoare방법으로 풀어야햇다.

직접 푼 풀이

재도전하기

느낀점

1. 결론적으로 못 풀었다. hoare's방법을 봤을때 이해했다고 생각했는데 직접 짜보지 않아서인지 이해한게 아니었다.
2. 근본적으로 lumoto와 접근방법이 다르다. lumoto는 요소하나를 중심으로 낮은거 높은거를 나누고 hoare는 그 중간요소를 찾는것부터 시작한다. 그 중간요소를 왼쪽 오른쪽으로부터 접근을 시작해서 찾고 그 다음에 그걸 중심으로 subarray를 재귀적으로 계산한다.
3. "347. Top K Frequent Elements"에서 hoare's를 익혔다고 생각했는데 아니었다. 다시 풀어보자.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    public void sortColors(int[] nums) {
        doSort(nums, 0, nums.length-1);
    }

    private void doSort(int[] nums, int start, int end) {        
        if (start >= end) {
            return;
        }

        int pivot = partition(nums, start, end);

        doSort(nums, start, pivot);
        doSort(nums, pivot+1, end);
    }

    private int partition(int[] nums, int start, int end) {
        int pivot = nums[(start+end)/2];
        int left = start-1;
        int right = end+1;
        int aaa = 0;
        while(true) {
            do {
                left++;
            } while (nums[left] < pivot);

            do {
                right--;
            } while (nums[right] > pivot);

            if (left >= right) {
                return right;
            }

            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }

    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)