문제 개요
정수로 이루어진 배열 A가 있다고 가정해 보겠습니다. 이때 짝수가 먼저 오고, 그 뒤에 홀수가 오도록 배열을 정렬해야 합니다.
예를 들어, 배열이 A = [1, 5, 6, 8, 7, 2, 3]이라면 결과는 [6, 8, 2, 5, 7, 1, 3]처럼 앞쪽에는 짝수(6, 8, 2), 뒤쪽에는 홀수(5, 7, 1, 3)가 배치되어야 합니다.
풀이 접근 방법
이 문제는 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 해결 과정은 다음과 같습니다.
- 두 개의 인덱스 i와 j를 모두 0으로 초기화합니다. i는 다음 짝수가 위치할 자리를 가리키는 역할을 합니다.
- j가 배열의 크기보다 작은 동안 반복합니다.
- arr[j]가 짝수라면 arr[i]와 arr[j]의 값을 서로 교환(swap)한 후, i를 1 증가시킵니다.
- 매 반복마다 j를 1 증가시켜 배열 전체를 순회합니다.
- 순회가 끝나면 arr을 반환합니다.
이 방식은 짝수를 만날 때마다 해당 값을 배열 앞쪽으로 옮겨주기 때문에, 최종적으로 짝수는 앞부분에, 홀수는 뒷부분에 자연스럽게 모이게 됩니다.
구현 예제
다음 코드를 통해 실제 구현을 살펴보겠습니다.
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()
nums = [1,5,6,8,7,2,3]
print(ob1.sortArrayByParity(nums))
입력
[1,5,6,8,7,2,3]
출력
[6,8,2,5,7,1,3]
복잡도 분석
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 되므로 매우 효율적입니다.
- 공간 복잡도: O(1) — 추가 메모리 없이 제자리(in-place)에서 정렬이 이루어집니다.