숫자로 이루어진 리스트 nums가 주어졌을 때, 다음 세 가지 조건을 만족하도록 배열을 정렬하는 문제입니다.
- 짝수는 오름차순으로 정렬합니다.
- 홀수는 내림차순으로 정렬합니다.
- 짝수와 홀수의 상대적인 위치(인덱스 순서)는 절대 변경되지 않아야 합니다.
예를 들어 입력이 [9, 14, 12, 91, -4, 5]라면 출력은 [91, -4, 12, 9, 14, 5]가 됩니다.
문제 해결 접근 방법
핵심 아이디어는 간단합니다. 짝수와 홀수를 각각 분리한 뒤 원하는 방향으로 정렬하고, 원래 배열에서 짝수였던 자리에는 정렬된 짝수를, 홀수였던 자리에는 정렬된 홀수를 순서대로 다시 채워 넣는 것입니다.
- evens : nums 배열에서 짝수만 추출한 리스트
- odds : nums 배열에서 홀수만 추출한 리스트
- evens 리스트를 오름차순으로 정렬
- odds 리스트를 내림차순으로 정렬
- 포인터 두 개(
even_i = 0,odd_i = 0)를 초기화 - index를 0부터 nums의 길이까지 반복하면서
- nums[index]가 짝수라면 → 해당 자리에 evens[even_i]를 넣고 even_i를 1 증가
- nums[index]가 홀수라면 → 해당 자리에 odds[odd_i]를 넣고 odd_i를 1 증가
- 정렬된 nums를 반환
이 방식을 사용하면 짝수와 홀수가 원래 있던 자리는 그대로 유지되면서, 각 그룹 내부에서만 원하는 순서로 재배치됩니다.
구현 예시
class Solution:
def solve(self, nums):
evens = [num for num in nums if num % 2 == 0]
odds = [num for num in nums if num % 2 != 0]
evens.sort()
odds.sort(reverse=True)
even_i = 0
odd_i = 0
for index in range(len(nums)):
if nums[index] % 2 == 0:
nums[index] = evens[even_i]
even_i += 1
else:
nums[index] = odds[odd_i]
odd_i += 1
return nums
ob = Solution()
print(ob.solve([9, 14, 12, 91, -4, 5]))
입력
[9, 14, 12, 91, -4, 5]
출력
[91, -4, 12, 9, 14, 5]
동작 과정 살펴보기
입력 [9, 14, 12, 91, -4, 5]에 대해 단계별로 확인해 보겠습니다.
- 짝수 추출:
[14, 12, -4]→ 오름차순 정렬 후[-4, 12, 14] - 홀수 추출:
[9, 91, 5]→ 내림차순 정렬 후[91, 9, 5] - 원래 배열에서 짝수 자리(1, 2, 4번 인덱스)에는
-4, 12, 14가 순서대로 들어갑니다. - 홀수 자리(0, 3, 5번 인덱스)에는
91, 9, 5가 순서대로 들어갑니다.
최종 결과는 [91, -4, 12, 9, 14, 5]로, 짝수는 오름차순, 홀수는 내림차순으로 정렬되면서도 각 수의 원래 위치가 그대로 유지됩니다.
시간 복잡도
짝수와 홀수를 분리하는 데 O(n), 각 리스트를 정렬하는 데 O(n log n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 추가 리스트 두 개를 사용하므로 공간 복잡도는 O(n)입니다.