[LeetCode 905] 원소들을 짝수를 전부 늘어놓은 다음 홀수를 배치

이 문제는 정수를 원소로 갖는 배열(array)을 O(n) 시간과 O(1) 기억공간을 사용해서 짝수가 모두 먼저 나오고 그 다음 홀수가 나오도록 재배치하는 문제이다. Easy임에도 요구조건을 맞추기가 쉽지 않다.

 

우선, 이 문제의 핵심은 배열을 짝수, 미분류, 홀수의 세 가지로 나누는 발상이다. 맨 처음 입력된 배열(A라고 부르자)은 전체가 미분류 상태이다. 이것을 O(n) 번 지나가면서 짝수, 홀수로 분류된 부분을 늘려가면 된다. 그러기 위해 짝수로 분류된 배열 부분과 홀수로 분류된 배열 부분을 가리킬 손가락 등 총 두 개의 포인터(even, odd)를 설정하고, 이것을 배열의 맨 앞과 뒤에 초기 배치한다.

 

그 다음, 맨 앞 원소부터 짝수인지 테스트하여, 만일 짝수라면 이것은 옳게 된 것이므로 짝수용 포인터(even)를 하나 전진한다. 만일 맨 앞 원소가 홀수라면, 이것은 맨 뒤 원소와 맞바꾼다음, 이제 맨 뒤의 홀수를 놓아야 하는 규칙이 충족되었으므로 맨 뒤에 있던 홀수 포인터(odd)를 하나 전진시켜 홀수로 분류된 부분이 늘어났음을 표시한다. 두 포인터가 가리키는 원소들이 비교 가능한 별개의 원소여야 하므로 even < odd 일 동안 비교를 시행한다.

 

그런데 맨 앞 원소가 짝수인지 홀수인지만 고려하고, 맨 뒤 원소가 어떻게 되든 상관을 하지 않는 것은 왜 그래도 될까. 왜냐면 맨 앞 원소가 짝수냐 홀수냐를 판정하면 loop 당 한 원소씩은 해결이 되는 것이 확실하기 때문이다. 만일 맨 앞 원소가 짝수라면 짝수 부분은 분류 한 개 끝났다. 만일 맨 앞 원소가 홀수라면 이를 뒤의 것과 바꿈으로써 홀수 부분도 분류가 한 개 끝났다. 바꾸었기 때문에 맨 뒤 원소가 홀수였는지 짝수였는지는 다음 loop에서 다시 판정하면 된다.

 

코드는 아래와 같다.

def even_odd(A):
    even, odd = 0, len(A) - 1
    while even < odd:
        if A[even] % 2 == 0:  # even
            even += 1
        else:  # odd, send it back
            A[even], A[odd] = A[odd], A[even]
            odd -= 1

그런데 이것을 양 끝의 원소가 다음의 4가지 쌍과 같은 조합인 경우로 나누어 생각하고 싶은 생각이 들 수도 있으나 그렇게 하면 안된다. 아래에 이유를 적어보았다.

	맨 앞	맨 뒤	설명
1	even	odd	이 경우는 목적한대로 옳게 되었으므로 포인터를 각기 들여쓰면 된다
2	even	even	이 경우는 맨 앞은 괜찮으나 맨 뒤가 잘못되었다. 일단 맨 앞을 하나 들여쓰고, 다음번 loop 에서 만일 맨 앞이 odd가 나오면 바로 아래 3번 경우가 된다.
3	odd	even	이때는 앞 뒤를 바꾸면 된다.
4	odd	odd	그러나 이번 경우는 애매하다. 맨 앞을 뒤와 바꾸어도 소용이 없고 그렇다고 일단 odd는 잠시 놔두고 나중에 해결하기로 하고 맨 뒤 포인터를 하나 감소시켜 다시 even/odd를 판정하여 3번인지 4번인지를 가려야 하는데, 3번이라면 괜찮으나, 4번이라면 다시 맨 뒤 포인터를 감소시켜야 한다. 그런 다음에는 다시 해결이 안된 곳들로 돌아가서 해결해야 하는데... 엄청 복잡하다.

이렇듯 확실한 것 하나만 해결하고 다음번 loop로 보내므로 결국 O(n) 시간과 O(1) 공간 안에 해결을 하게 된다.