[LeetCode_JS] 75. Sort Colors _array

문제

Leetcode Sort Colors 문제

- input: 숫자 0, 1, 2로 이뤄진 배열

- output: void,

- 주의: 카피하지 않고 nums 배열을 in-place로 swap해서 sort

 

풀이

런타임: 71ms / 86.69%   (주로 70ms대로 나옴)

메모리: 38MB / 98.00%

var sortColors = function(nums) {
    let zeroP = 0;
    let twoP = nums.length - 1;
    
    for(let i = 0; i < nums.length; i++) {
        if(twoP < i) break;
        else if(nums[i] === 0) {
            nums[i] = nums[zeroP]
            nums[zeroP] = 0;
            zeroP++;
            if(zeroP-1 === i) continue;   // *
        } 
        else if(nums[i] === 2) {
            nums[i] = nums[twoP]
            nums[twoP] = 2;
            twoP--;
        }
        if(nums[i] === 0 || nums[i] === 2) i--;  // **
    }
};

zeroP의 왼쪽은 모두 0이고, twoP의 오른쪽은 모두 2만 있을 수 있다.

즉, 0 다음 인덱스를 가리키는 포인터가 zeroP이고, 2 이전 인덱스를 가리키는 포인터가 twoP이다.

i는 반복문을 돌면서 원소 하나씩 돌면서 체크하고, 0이나 2일 경우 swap한다.

 

이 때, (**)swap한 이후 바뀐 값(nums[i])이 또 0이나 2일 수 있다!

그래서 마지막에 if문으로 검사해주고, i가 증가하지 않은 상태에서 한 번 더 swap할 수 있도록 한다.

 

(*)zeroP와 i가 같을 때는 바뀐 nums[i]값이 무조건 0이므로 바로 i++이 될 수 있도록 continue해준다.

(nums[i]값을 if문으로 체크해 i--가 되지 않도록. 즉, i가 그대로인 상태에서 또 체크하지 않도록)

 

---

리팩토링 전 풀이

위처럼 풀기 전에, i--하면 i값은 그대로인 상태에서 for문을 한 번 더 돌게 되는데 이걸 생각을 못 하고....

함수로 빼서 재귀를 돌도록 했었다..

var sortColors = function(nums) {
    let zeroP = 0;
    let twoP = nums.length - 1;
    
    for(let i = 0; i < nums.length; i++) {
        const res = check(nums, i, zeroP, twoP);
        if(!res) break;
        [zeroP, twoP] = res;
    }
};

const check = (nums, i, zeroP, twoP) => {
    if(twoP < i) return null;
    else if(nums[i] === 0) {
        nums[i] = nums[zeroP]
        nums[zeroP] = 0;
        if(zeroP === i) return [zeroP+1, twoP];
        zeroP++;
    } 
    else if(nums[i] === 2) {
        nums[i] = nums[twoP]
        nums[twoP] = 2;
        twoP--;
    }
    if(nums[i] === 0 || nums[i] === 2) check(nums, i, zeroP, twoP)
    return [zeroP, twoP];
}

코드가 지저분할 뿐더러 런타임은 72~124까지 왔다갔다하고, 메모리는 7%..;;

그래서 리팩토링을 해서 위코드로 바꾼 것.

지저분한 코드이고 부끄럽긴 하지만 그래도 기록해놓는 게 좋을 것 같아 올려는 놓는다.

 

---

참고📚

유튜브 - 코드없는 프로그래밍 Sort Colors