문제 개요
숫자로 이루어진 리스트 nums가 주어졌을 때, 리스트에 등장하는 연속된 짝수 정수 두 개를 서로 교환하는 문제입니다.
예를 들어, 입력이 다음과 같다면:
nums = [4, 5, 6, 8, 10]
출력은 아래와 같습니다.
[6, 5, 4, 10, 8]
위 예시에서 4와 6이 첫 번째 연속 짝수 쌍이므로 서로 자리를 바꾸고, 8과 10이 두 번째 연속 짝수 쌍이므로 역시 서로 교환됩니다. 그 사이의 홀수인 5는 그대로 유지됩니다.
해결 접근 방법
이 문제는 한 번의 순회만으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 아직 짝이 없는 짝수의 인덱스를 저장할 임시 변수
temp를 준비합니다. 초기값은None입니다. - 리스트를 처음부터 끝까지 순회하면서 각 요소를 확인합니다.
- 현재 요소가 짝수라면:
temp에 저장된 이전 짝수가 있다면 두 요소의 위치를 서로 교환한 뒤,temp를 다시None으로 초기화합니다.- 저장된 짝수가 없다면 현재 인덱스를
temp에 저장하여 다음 짝수를 기다립니다.
- 순회가 끝나면 수정된 리스트를 반환합니다.
이 방식은 리스트를 딱 한 번만 훑기 때문에 시간 복잡도는 O(n), 추가 메모리 사용량은 상수 수준인 O(1)로 매우 효율적입니다.
구현 예제
아래는 위 알고리즘을 Python 클래스로 구현한 코드입니다.
class Solution:
def solve(self, nums):
temp = None
for i in range(len(nums)):
if nums[i] % 2 == 0:
if temp is not None:
nums[i], nums[temp] = nums[temp], nums[i]
temp = None
else:
temp = i
return nums
ob = Solution()
print(ob.solve([4, 5, 6, 8, 10]))입력
[4, 5, 6, 8, 10]
출력
[6, 5, 4, 10, 8]
코드 동작 원리 살펴보기
입력 [4, 5, 6, 8, 10]을 기준으로 코드의 실행 흐름을 단계별로 확인해 보겠습니다.
- i = 0: nums[0] = 4는 짝수이고 temp가 비어 있으므로, temp = 0으로 저장합니다.
- i = 1: nums[1] = 5는 홀수이므로 아무 작업도 하지 않습니다.
- i = 2: nums[2] = 6은 짝수이고 temp = 0이 저장되어 있으므로, nums[0]과 nums[2]를 교환합니다. 리스트는
[6, 5, 4, 8, 10]이 되고, temp는 None으로 초기화됩니다. - i = 3: nums[3] = 8은 짝수이고 temp가 비어 있으므로, temp = 3으로 저장합니다.
- i = 4: nums[4] = 10은 짝수이고 temp = 3이 저장되어 있으므로, nums[3]과 nums[4]를 교환합니다. 최종 결과는
[6, 5, 4, 10, 8]입니다.
마무리
이처럼 임시 변수 하나만 활용하면 연속된 짝수 쌍을 손쉽게 찾아 교환할 수 있습니다. 투 포인터 기법의 변형으로 볼 수 있는 이 패턴은 배열 내에서 특정 조건을 만족하는 요소들을 짝지어 처리하는 다양한 문제에도 응용할 수 있으니 잘 기억해 두면 좋습니다.