파이썬으로 보완 배열(Complementary Array)을 만드는 최소 이동 횟수 구하기

짝수 길이의 배열 nums와 하나의 값 limit이 주어져 있다고 가정해 봅시다. 한 번의 이동(move)으로 nums 안의 임의의 값을 1부터 limit까지(양 끝값 포함) 범위에 있는 다른 값으로 교체할 수 있습니다.

모든 인덱스 i에 대해 nums[i] + nums[n-1-i]가 서로 동일한 값을 가질 때, 이 배열을 보완 배열(complementary)이라고 부릅니다. 즉, 배열의 양끝에서부터 짝지은 요소들의 합이 전부 같아야 한다는 의미입니다. 우리가 구해야 하는 것은 nums를 보완 배열로 만들기 위해 필요한 최소 이동 횟수입니다.

문제 예시

입력이 nums = [1,4,2,3], limit = 4라고 해보겠습니다. 이 경우 출력은 1입니다. 한 번의 이동으로 인덱스 1의 요소(4)를 2로 바꾸면 배열은 [1,2,2,3]이 되고, 다음과 같이 모든 짝의 합이 4로 일치하기 때문입니다.

nums[0] + nums[3] = 1 + 3 = 4
nums[1] + nums[2] = 2 + 2 = 4

해결 접근 방식

목표 합(target)을 2부터 2×limit까지 하나씩 시도하면서, 각 target마다 필요한 이동 횟수를 계산하는 것이 핵심 아이디어입니다. 각 짝 (x, y)에 대해 다음 세 가지 경우로 나눌 수 있습니다.

x + y == target인 경우: 이동이 전혀 필요 없습니다 (0회).
target이 [min(x,y)+1, max(x,y)+limit] 구간에 속하는 경우: 두 요소 중 하나만 바꾸면 되므로 1회 이동이면 충분합니다.
그 외의 경우: 두 요소를 모두 바꿔야 하므로 2회 이동이 필요합니다.

구간 시작점과 끝점을 각각 기록해 누적합(차분 배열) 방식으로 처리하면, 각 target에 대해 "1회 이동으로 커버되는 짝의 수"를 효율적으로 구할 수 있습니다.

알고리즘 단계

이 문제를 해결하려면 다음 단계를 따릅니다.

n := nums의 크기
mid := n / 2의 몫
zero_moves := 정수 값을 저장하는 빈 맵(딕셔너리)
start := 크기가 (2 * limit + 1)인 배열, 0으로 초기화
end := 크기가 (2 * limit + 1)인 배열, 0으로 초기화
res := 무한대(infinity)
i를 0부터 mid-1까지 반복:
- x := nums[i]
- y := nums[n - 1 - i]
- zero_moves[x + y] := zero_moves[x + y] + 1
- start[1 + min(x, y)]를 1 증가
- end[limit + max(x, y)]를 1 증가
intervals := 0
target을 2부터 limit*2까지 반복:
- intervals := intervals + start[target]
- cost := 2 * (mid - intervals) + intervals - zero_moves[target]
- res := res와 cost 중 최솟값
- intervals := intervals - end[target]
res 반환

여기서 cost 계산식을 살펴보면, 커버되지 않은 짝(mid - intervals)은 각각 2번의 이동이 필요하고, 커버된 짝(intervals) 중 이미 합이 target인 경우(zero_moves[target])는 이동이 필요 없으므로 이를 차감하는 방식입니다.

구현 예시

더 나은 이해를 위해 다음 파이썬 구현을 살펴보겠습니다.

from collections import defaultdict
def solve(nums, limit):
    n = len(nums)
    mid = n // 2

    zero_moves = defaultdict(int)

    start = [0] * (2 * limit + 1)
    end = [0] * (2 * limit + 1)
    res = float('inf')
    for i in range(mid):
        x = nums[i]
        y = nums[n - 1 - i]
        zero_moves[x + y] += 1
        start[min(x, y) + 1] += 1
        end[max(x, y) + limit] += 1

    intervals = 0
    for target in range(2, limit * 2 + 1):
        intervals += start[target]
        cost = 2 * (mid - intervals) + intervals - zero_moves[target]
        res = min(res, cost)
        intervals -= end[target]
    return res

nums = [1,4,2,3]
limit = 4
print(solve(nums, limit))

입력

[1,4,2,3], 4