길이가 짝수인 숫자 리스트 nums가 주어져 있다고 가정해 보겠습니다. 우리는 리스트 안에서 임의의 숫자 하나를 골라 1부터 nums의 최댓값 사이의 값으로 바꾸는 연산을 수행할 수 있습니다. 이때 모든 인덱스 i에 대해 nums[i] + nums[n-1-i]의 값이 서로 같아지도록 만들기 위해 필요한 최소 연산 횟수를 구하는 것이 이 문제의 목표입니다.
예를 들어 입력이 nums = [8,6,2,5,9,2]라면 출력은 2가 됩니다. nums[2]의 2를 5로, nums[4]의 9를 4로 바꾸면 리스트는 [8,6,5,5,4,2]가 되고, 각 i에 대한 nums[i] + nums[n-1-i]는 (8+2) = (6+4) = (5+5) = 10으로 모두 같아지기 때문입니다.
접근 방법
이 문제는 스윕(sweep) 기법으로 효율적으로 해결할 수 있습니다. 목표 합 S를 하나 정했을 때, 각 쌍 (a, b)에 필요한 연산 횟수는 다음과 같이 결정됩니다.
- a + b == S이면 연산이 전혀 필요 없습니다 (0회).
- 한쪽 요소만 바꿔서 S를 만들 수 있으면, 즉 S가 [다른 쪽 값 + 1, 다른 쪽 값 + 최댓값] 범위 안에 있으면 1회입니다.
- 그 외의 경우에는 양쪽을 모두 바꿔야 하므로 2회입니다.
전체 비용은 "2 × 짝의 개수"에서 "S를 한 번 이하의 연산으로 맞출 수 있는 짝의 수와 정확히 일치하는 짝의 수의 합"을 뺀 값이 됩니다. 따라서 후보 합 S를 왼쪽에서 오른쪽으로 훑으면서 이 기여도를 누적하고, 그 최댓값을 찾으면 최소 연산 횟수를 알 수 있습니다.
이를 위해 다음 단계를 따릅니다.
- N := nums의 길이
- mx := nums의 최댓값
- events := 새로운 리스트
- idx := 0
- idx < N / 2의 내림인 동안 반복:
- a := nums[idx]
- b := nums[N - idx - 1]
- (min(a + 1), (b + 1)의 최솟값, 1)을 events 끝에 삽입 → 한쪽만 변경 가능한 구간의 시작
- (a + b, 1)을 events 끝에 삽입 → 연산 없이 일치하는 지점
- (a + b + 1, -1)을 events 끝에 삽입 → 일치 지점의 종료
- (max(a + mx), (b + mx)의 최댓값 + 1, -1)을 events 끝에 삽입 → 한쪽 변경 구간의 종료
- idx := idx + 1
- events 리스트를 정렬
- current := 0, mx_same := 0
- events의 각 (event, delta)에 대해:
- current := current + delta
- mx_same := current와 mx_same 중 큰 값
- N - mx_same 반환
예제 코드
아래 구현을 통해 더 잘 이해해 보겠습니다.
def solve(nums):
N = len(nums)
mx = max(nums)
events = []
idx = 0
while idx < N // 2:
a = nums[idx]
b = nums[N - idx - 1]
# 한쪽 요소만 변경해 만들 수 있는 구간의 시작
events.append((min(a + 1, b + 1), 1))
# 연산 없이 두 수의 합이 정확히 일치하는 지점
events.append((a + b, 1))
events.append((a + b + 1, -1))
# 한쪽 요소만 변경 가능한 구간의 종료
events.append((max(a + mx, b + mx) + 1, -1))
idx += 1
events.sort()
current = 0
mx_same = 0
for event, delta in events:
current += delta
mx_same = max(current, mx_same)
return N - mx_same
nums = [8, 6, 2, 5, 9, 2]
print(solve(nums))입력
[8, 6, 2, 5, 9, 2]
출력
2
복잡도 분석
각 짝마다 상수 개수의 이벤트를 생성하므로 이벤트 수는 N개이고, 정렬에 지배적인 시간이 걸립니다. 따라서 시간 복잡도는 O(N log N), 공간 복잡도는 O(N)입니다. 리스트 길이가 커져도 효율적으로 동작하는 접근 방식입니다.