숫자로 이루어진 배열 A가 있을 때, 배열 안의 숫자들을 짝수가 먼저 오고 그 뒤에 홀수가 오도록 재배치해야 하는 문제를 생각해 볼 수 있습니다.
예를 들어 배열이 A = [1, 5, 6, 8, 7, 2, 3]이라면, 결과는 [6, 8, 2, 1, 5, 7, 3]처럼 앞쪽에는 짝수, 뒤쪽에는 홀수가 배치되어야 합니다.
해결 접근 방식
이 문제는 두 포인터(two pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.
- 포인터 i와 j를 모두 0으로 초기화합니다.
- j가 배열의 길이보다 작은 동안 반복합니다.
- 만약 arr[j]가 짝수라면, arr[i]와 arr[j]의 값을 서로 교환(swap)하고 i를 1 증가시킵니다.
- 그다음 j를 1 증가시킵니다.
- 반복이 끝나면 배열을 반환합니다.
여기서 i는 '짝수가 확정된 영역의 다음 위치'를 가리키고, j는 현재 검사 중인 원소를 가리킵니다. 덕분에 한 번의 순회(O(n))만으로 배열 전체를 패리티 기준으로 나눌 수 있습니다.
구현 예제
아래는 위 알고리즘을 파이썬 클래스로 구현한 코드입니다.
class Solution(object):
def sortArrayByParity(self, a):
i = 0
j = 0
while j < len(a):
if a[j] % 2 == 0:
a[i], a[j] = a[j], a[i]
i += 1
j += 1
return a
ob1 = Solution()
print(ob1.sortArrayByParity([1, 5, 6, 8, 7, 2, 3]))
입력
[1, 5, 6, 8, 7, 2, 3]
출력
[6, 8, 2, 5, 7, 1, 3]
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하므로 매우 효율적입니다.
- 공간 복잡도: O(1) — 추가 배열 없이 제자리(in-place)에서 교환만 수행합니다.
참고로 이 방식은 짝수끼리의 상대적 순서까지는 보장하지 않는 불안정(unstable) 정렬입니다. 만약 각 그룹 내부의 원래 순서를 유지해야 한다면, 리스트 컴프리헨션을 사용해 [x for x in a if x % 2 == 0] + [x for x in a if x % 2 != 0]처럼 새 리스트를 만드는 방법도 고려할 수 있습니다.