[자료구조와 알고리즘] 27. Remove Element (Feat. 제자리 알고리즘)

문제 설명

문제 링크: LeetCode Top Interview 150 - 27. Remove Element

간단히 설명하자면,
주어진 숫자 배열 nums에서 어떤 숫자 val와 같은 값이 있다면 그 부분을 제외하고
배열의 남은 숫자 갯수를 반환하고, nums는 남은 숫자들을 앞쪽으로 재배열하는 문제입니다.

조금 특이한 점이 있다면 nums배열에서 남은 숫자들이 앞쪽에만 배치되어 있다면 남은 뒷부분은 신경쓰지 않아도 되고 배열의 길이가 달라져도👀 괜찮습니다.

풀어보기

문제에서 요구한 알고리즘이 in-place 제자리 알고리즘이기 때문에 최대한 추가적인 메모리를 사용하지 않고! 풀어봐야겠습니다.

제자리 알고리즘 : 컴퓨터 과학에서 제자리(in-place) 알고리즘은 자료 구조를 추가로 사용하지 않고 입력을 변환하는 알고리즘이다. 그러나 보통 추가적인 변수를 위해 약간의 추가 저장 공간은 허용된다. 일반적으로 알고리즘이 실행되면서 입력 값이 출력 값으로 덮어써지는데 입력 요소를 출력 요소로 교체하거나 요소의 위치를 바꾸는 방식으로 업데이트한다.
제자리라는 말은 조금씩 다른 의미를 가질 수 있는데, 가장 엄격하게는 함수 호출 및 포인터까지 포함하여 고정된 양의 추가 공간만 가지는 것을 의미한다. 그러나 ... 일반적으로 이 공간은 O(log n)이지만 때로는 O(n)까지도 허용된다.
출처: 위키백과

function removeElement(nums: number[], val: number): number {
    let countK = 0;     // 반환되는 값을 위한 추가적인 변수!
    for (let i=0; i<nums.length; i++) {
        if (nums[i] === val) {
            nums[i] = undefined;  // 배열에서 val을 제거합니다 
        } else {
            countK++;
        }
    }
    nums.sort();  // 남은 숫자들을 앞쪽으로 배열하기 위해서 정렬합니다

    return countK;
};

문제에서는 val과 다른 숫자 요소는 k라고 부르고 있어서 반환하는 값의 변수를 countK라고 정했습니다.

더 좋은 코드

일단은 배열에서 요소를 제거하기위해서만 풀어보았는데 제자리 알고리즘을 제대로 활용한 좋은 코드를 발견했습니다..! 어차피 반환해야되는 K요소의 갯수를 nums 배열의 인덱스로 활용하는 방법입니다.
사실 문제에서는 배열에서 요소를 제거하라고 했지만 채점할 때 실제로 val 요소가 제거되어 있지 않아도 괜찮기 때문에 제자리 알고리즘을 사용한 더 좋은 코드라고 생각합니다.

function removeElement(nums: number[], val: number): number {
    let countK = 0;
    for( let n of nums )if( n !== val ) nums[countK++] = n;

    return countK;
};

마무리

문제 난이도가 높지 않기 때문에 제자리 알고리즘을 이해하기에 좋은 문제라고 생각합니다. 🥰