Remove Element — 앞쪽 유효 구간으로 압축하는 제자리 제거

특정 값을 지운 뒤 남은 길이를 구하기, 어떤 문제인가요?

LeetCode 27번 문제는 이렇게 주어집니다.

정수 배열 nums와 정수 val이 주어집니다. nums에서 val과 같은 모든 값을 제자리(in-place) 에서 제거하고, val이 아닌 원소 개수 k를 반환하세요.

정답으로 인정되려면:

• nums의 앞쪽 k개에 val이 아닌 값들이 들어 있어야 하고
• 그 뒤쪽 값들은 무엇이든 상관없습니다

예시는 이렇습니다.

• nums = [3,2,2,3], val = 3 → k = 2, nums[:2] = [2,2]
• nums = [0,1,2,2,3,0,4,2], val = 2 → k = 5, nums[:5]에는 0,0,1,3,4가 어떤 순서로든 들어 있으면 됨

제약은 다음과 같습니다.

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

이 문제의 핵심은 "배열에서 값을 완전히 지운다"가 아니라, 앞쪽 구간을 유효한 값들로 압축한다는 점입니다. 이 글에서는 별도 배열을 쓰는 직관적인 풀이부터, 쓰기 포인터로 앞쪽 구간을 유지하는 O(n)/O(1) 풀이, 그리고 제거할 값이 드물 때 유용한 뒤쪽 스왑 변형까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

문제를 "새 길이 k를 만드는 것"으로 보기

이 문제는 배열 길이를 실제로 줄이지 않습니다. 대신:

앞의 k칸은 유효한 값
뒤의 나머지는 무시

라는 상태를 만드는 것이 목표입니다.

예를 들어:

nums = [3, 2, 2, 3], val = 3

이면 최종적으로 중요한 것은:

[2, 2, _, _]

처럼 앞의 2칸이 2, 2로 채워져 있는가입니다. 뒤의 _ 부분은 어떤 값이 남아 있어도 상관없습니다.

즉 이 문제는 사실상:

val이 아닌 원소만 앞쪽으로 모으고
그 개수를 반환하라

로 볼 수 있습니다.

Phase 1. 새 배열에 모아서 복사하기

가장 먼저 떠올릴 수 있는 방법은 val이 아닌 값들만 새 배열에 모으는 것입니다.

fun removeElement(nums: IntArray, `val`: Int): Int {
    val result = IntArray(nums.size)
    var k = 0

    for (num in nums) {
        if (num != `val`) {
            result[k++] = num
        }
    }

    for (i in 0 until k) {
        nums[i] = result[i]
    }

    return k
}

nums = [3,2,2,3], val = 3이라면:

• 2, 2만 result에 모음
• nums[0], nums[1]에 복사
• k = 2 반환

정답은 맞지만, 문제는 제자리 수정을 요구합니다. 이 방식은 result 배열 때문에 O(n) 추가 공간이 듭니다.

Phase 2. 쓰기 포인터로 앞쪽 유효 구간 유지하기

별도 배열 없이 하려면, "다음에 유효한 값을 쓸 위치"를 가리키는 포인터 하나만 두면 됩니다.

fun removeElement(nums: IntArray, `val`: Int): Int {
    var write = 0

    for (read in nums.indices) {
        if (nums[read] != `val`) {
            nums[write] = nums[read]
            write++
        }
    }

    return write
}

여기서 의미는 이렇습니다.

• read: 원본 배열을 왼쪽에서 오른쪽으로 읽는 포인터
• write: val이 아닌 값을 써야 할 다음 위치

nums = [0,1,2,2,3,0,4,2], val = 2를 따라가 봅시다.

read=0 -> 0 != 2 -> nums[0]=0, write=1
read=1 -> 1 != 2 -> nums[1]=1, write=2
read=2 -> 2 == 2 -> 건너뜀
read=3 -> 2 == 2 -> 건너뜀
read=4 -> 3 != 2 -> nums[2]=3, write=3
read=5 -> 0 != 2 -> nums[3]=0, write=4
read=6 -> 4 != 2 -> nums[4]=4, write=5
read=7 -> 2 == 2 -> 건너뜀

최종적으로:

nums[:5] = [0, 1, 3, 0, 4]
k = 5

가 됩니다.

문제 조건상 앞의 5개만 맞으면 되므로 정답입니다.

시간 복잡도는 O(n)이고, 추가 공간은 O(1)입니다.

왜 이 방식이 맞나요?

반복문이 진행되는 동안 항상 다음 불변식이 유지됩니다.

nums[0 .. write-1]에는 지금까지 본 원소 중
val이 아닌 값들이 순서대로 들어 있다

새 원소를 읽을 때:

• val이면 버림
• val이 아니면 write 위치에 복사하고 write++

하면 이 불변식이 계속 유지됩니다.

반복이 끝나면 전체 배열을 다 확인했으므로, nums[0 .. write-1]는 전체 유효 원소 구간이 됩니다. 따라서 반환값 write가 곧 정답 k입니다.

Move Zeroes와 어떤 차이가 있나요?

Move Zeroes는 0이 아닌 원소의 상대 순서 유지가 필수였습니다. 그래서 앞쪽에 모으는 과정에서 순서를 보존해야 했습니다.

이 문제는 조금 다릅니다.

• 앞쪽 k칸에 val이 아닌 값만 있으면 됨
• 문제 설명상 순서는 바뀌어도 됨

즉 Phase 2 풀이는 순서를 유지하지만, 사실 그보다 더 공격적인 최적화도 가능합니다.

Phase 3. 제거할 값이 드물다면 뒤쪽 스왑도 가능

문제에서 순서를 요구하지 않으므로, 제거할 값을 만났을 때 뒤쪽의 아직 처리되지 않은 값과 바꾸는 방법도 있습니다.

fun removeElement(nums: IntArray, `val`: Int): Int {
    var left = 0
    var right = nums.size

    while (left < right) {
        if (nums[left] == `val`) {
            nums[left] = nums[right - 1]
            right--
        } else {
            left++
        }
    }

    return left
}

이 풀이는:

• left는 현재 확인 중인 위치
• right는 아직 유효할 수 있는 구간의 끝 다음 위치

를 뜻합니다.

nums[left] == val이면 그 값은 제거해야 하므로, 뒤쪽 마지막 후보를 가져와 덮어씁니다. 그리고 right-- 해서 유효 구간을 줄입니다.

중요한 점은 이때 left++를 바로 하지 않는다는 것입니다. 방금 뒤에서 가져온 값도 다시 검사해야 하기 때문입니다.

이 방식은 제거할 값이 적고 배열 뒤쪽 값으로 빠르게 덮어써도 되는 상황에서 유리합니다. 다만 순서가 보존되지 않으므로, 설명하기에는 Phase 2가 더 기본적이고 읽기 쉽습니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	val	결과	이유
[]	0	0	빈 배열
[3,2,2,3]	3	2	2,2 두 개만 남음
[0,1,2,2,3,0,4,2]	2	5	2가 아닌 값 5개
[1,1,1]	1	0	전부 제거 대상
[1,2,3]	4	3	제거할 값이 없음

특히 k = 0인 경우가 중요합니다. 모든 값이 제거 대상이면 앞쪽 유효 구간은 길이 0이 되고, 배열 안의 나머지 값은 아무 의미가 없습니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
새 배열에 모아 복사	O(n)	O(n)	직관적이지만 제자리 조건을 만족하지 못함
쓰기 포인터로 앞쪽 압축	O(n)	O(1)	가장 기본적인 제자리 풀이, 순서도 유지됨
뒤쪽 스왑	O(n)	O(1)	순서를 버리고 제거를 더 직접적으로 수행

마무리

1. 이 문제의 본질은 배열 길이를 줄이는 것이 아니라 앞쪽 유효 구간의 길이 k를 만드는 것입니다 — 뒤쪽 값은 신경 쓸 필요가 없습니다
2. 쓰기 포인터 풀이에서는 nums[0 .. write-1]가 항상 유효 구간이라는 불변식이 핵심입니다 — 읽으면서 바로 압축할 수 있습니다
3. 이 방식은 O(n) 시간, O(1) 공간으로 문제 요구를 정확히 만족합니다 — 가장 기본적인 정답입니다
4. 문제는 순서 보존을 요구하지 않으므로 뒤쪽 스왑 변형도 가능합니다 — 제거할 값이 드문 상황에서 유용할 수 있습니다
5. Move Zeroes와 비슷해 보여도 요구 조건이 다릅니다 — 여기서는 앞쪽 k칸만 맞으면 되고, 뒤는 완전히 무시됩니다