Sort Array By Parity — 짝수를 앞쪽으로 모으기

짝수를 앞쪽으로 모으기, 어떤 문제인가요?

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

정수 배열 nums가 주어집니다. 모든 짝수가 배열의 앞쪽에 오고, 모든 홀수가 그 뒤에 오도록 배열을 반환하세요.

정답은 하나로 정해져 있지 않습니다. 조건만 만족하면 어떤 배열이든 가능합니다.

예시는 이렇습니다.

• nums = [3,1,2,4] → [2,4,3,1]
• [4,2,3,1], [2,4,1,3], [4,2,1,3]도 모두 정답
• nums = [0] → [0]

제약은 다음과 같습니다.

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

이 문제의 핵심은 숫자를 오름차순으로 정렬하는 것이 아닙니다. 짝수 그룹을 앞에, 홀수 그룹을 뒤에 두는 partition 문제입니다. 이 글에서는 새 배열을 만드는 풀이부터, 쓰기 포인터로 짝수를 앞으로 보내는 풀이, 양쪽 포인터로 제자리에서 교환하는 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

정렬이 아니라 분리입니다

문제 이름에는 Sort가 들어가지만, 실제로는 숫자 크기 순서로 정렬하지 않습니다.

필요한 조건은 이것뿐입니다.

[짝수들..., 홀수들...]

예를 들어:

nums = [3, 1, 2, 4]

정답으로 가능한 배열은 여러 개입니다.

[2, 4, 3, 1]
[4, 2, 3, 1]
[2, 4, 1, 3]
[4, 2, 1, 3]

짝수 내부의 순서나 홀수 내부의 순서는 중요하지 않습니다. 그래서 전체 정렬을 할 필요가 없습니다.

Phase 1. 새 배열에 짝수부터 담기

가장 직관적인 방법은 새 배열을 만들고 짝수를 먼저 넣은 뒤, 홀수를 넣는 것입니다.

fun sortArrayByParity(nums: IntArray): IntArray {
    val result = IntArray(nums.size)
    var index = 0

    for (num in nums) {
        if (num % 2 == 0) {
            result[index] = num
            index++
        }
    }

    for (num in nums) {
        if (num % 2 == 1) {
            result[index] = num
            index++
        }
    }

    return result
}

nums = [3,1,2,4]라면:

• 첫 번째 순회에서 2, 4를 넣음
• 두 번째 순회에서 3, 1을 넣음
• 결과는 [2,4,3,1]

이 방식은 이해하기 쉽습니다. 하지만 result 배열을 따로 만들기 때문에 추가 공간이 O(n)입니다.

시간 복잡도는 배열을 두 번 훑으므로 O(n)입니다.

Phase 2. 쓰기 포인터로 짝수를 앞으로 보내기

새 배열 없이 하려면 nums 앞쪽을 짝수 구간으로 사용하면 됩니다.

fun sortArrayByParity(nums: IntArray): IntArray {
    var write = 0

    for (read in nums.indices) {
        if (nums[read] % 2 == 0) {
            val temp = nums[write]
            nums[write] = nums[read]
            nums[read] = temp
            write++
        }
    }

    return nums
}

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

• read: 배열을 왼쪽에서 오른쪽으로 읽는 위치
• write: 다음 짝수를 놓아야 할 위치

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

처음: nums = [3, 1, 2, 4], write = 0

read=0 -> 3은 홀수 -> 그대로 둠
read=1 -> 1은 홀수 -> 그대로 둠
read=2 -> 2는 짝수 -> nums[0]과 nums[2] 교환
nums = [2, 1, 3, 4], write = 1

read=3 -> 4는 짝수 -> nums[1]과 nums[3] 교환
nums = [2, 4, 3, 1], write = 2

최종적으로 앞쪽에는 짝수, 뒤쪽에는 홀수가 모입니다.

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

Phase 3. 양쪽 포인터로 제자리 교환하기

짝수는 앞에, 홀수는 뒤에 있어야 하므로 양쪽 끝에서 포인터를 움직이는 방법도 자연스럽습니다.

fun sortArrayByParity(nums: IntArray): IntArray {
    var left = 0
    var right = nums.lastIndex

    while (left < right) {
        if (nums[left] % 2 == 0) {
            left++
        } else if (nums[right] % 2 == 1) {
            right--
        } else {
            val temp = nums[left]
            nums[left] = nums[right]
            nums[right] = temp
            left++
            right--
        }
    }

    return nums
}

포인터의 역할은 이렇습니다.

• left: 앞쪽에 있는데 아직 확인이 필요한 위치
• right: 뒤쪽에 있는데 아직 확인이 필요한 위치

각 상황은 세 가지입니다.

• nums[left]가 짝수면 이미 앞쪽에 있어도 되므로 left++
• nums[right]가 홀수면 이미 뒤쪽에 있어도 되므로 right--
• nums[left]는 홀수이고 nums[right]는 짝수면 둘을 교환

nums = [3,1,2,4]라면:

left=0, right=3
nums[left]=3 홀수, nums[right]=4 짝수 -> 교환
[4, 1, 2, 3]

left=1, right=2
nums[left]=1 홀수, nums[right]=2 짝수 -> 교환
[4, 2, 1, 3]

이 배열도 조건을 만족하므로 정답입니다.

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

두 포인터 풀이가 맞는 이유

반복문이 진행되는 동안 다음 상태를 유지합니다.

left 왼쪽 구간에는 짝수만 있음
right 오른쪽 구간에는 홀수만 있음

아직 정리되지 않은 구간은 left..right입니다.

[짝수 구간][아직 모름][홀수 구간]

left가 짝수면 짝수 구간을 한 칸 늘릴 수 있습니다. right가 홀수면 홀수 구간을 한 칸 늘릴 수 있습니다. 둘 다 잘못된 위치에 있을 때만 교환하면 됩니다.

반복이 끝나면 아직 모르는 구간이 사라지고, 배열은 짝수 구간과 홀수 구간으로 나뉩니다.

엣지 케이스

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

입력	가능한 결과	이유
[0]	[0]	원소 하나, 0은 짝수
[3,1,2,4]	[2,4,3,1]	기본 예시
[2,4,6]	[2,4,6]	이미 모두 짝수
[1,3,5]	[1,3,5]	모두 홀수라 앞쪽 짝수 구간이 비어 있음
[1,2]	[2,1]	홀수와 짝수 위치 교환
[2,1]	[2,1]	이미 조건 만족

이 문제는 결과가 하나로 고정되지 않습니다. 그래서 테스트할 때도 특정 배열 하나만 기대하기보다, "짝수 뒤에 홀수가 다시 나오지 않는가"를 확인하는 관점이 더 정확합니다.

세 풀이를 다시 비교

풀이	시간	공간	특징
새 배열에 짝수, 홀수 순서로 담기	O(n)	O(n)	가장 직관적
쓰기 포인터로 짝수 앞으로 이동	O(n)	O(1)	한쪽에서 읽으며 제자리 교환
양쪽 포인터로 교환	O(n)	O(1)	partition 의도가 가장 직접적

마무리

1. 이 문제는 숫자 크기 정렬이 아니라 짝수와 홀수를 나누는 문제입니다 — 조건은 [짝수들..., 홀수들...]입니다
2. 정답 배열은 여러 개 가능합니다 — 짝수끼리의 순서, 홀수끼리의 순서는 중요하지 않습니다
3. 보조 배열을 쓰면 짝수를 먼저 담고 홀수를 나중에 담으면 됩니다 — 이해하기 쉽지만 공간이 O(n)입니다
4. 제자리 풀이는 투 포인터 partition으로 해결할 수 있습니다 — 잘못된 위치의 홀수와 짝수를 교환하면 됩니다
5. 최종 풀이는 O(n) 시간, O(1) 공간입니다 — 배열을 한 번 훑는 수준으로 충분합니다