파이썬(Python)으로 배열 양 끝 요소를 제거해 X를 0으로 만드는 최소 연산 횟수 구하기

문제 설명

nums라는 배열과 값 x가 주어졌다고 가정해 봅시다. 한 번의 연산에서는 배열의 가장 왼쪽 또는 가장 오른쪽 요소를 삭제하고, 그 값을 x에서 뺄 수 있습니다. 우리의 목표는 x를 정확히 0으로 만들기 위해 필요한 최소 연산 횟수를 구하는 것이며, 만약 불가능하다면 -1을 반환해야 합니다.

예시 이해하기

예를 들어 nums = [4,2,9,1,4,2,3], x = 9라고 입력이 주어지면 출력은 3이 됩니다. 과정은 다음과 같습니다.

1. 먼저 가장 왼쪽 요소 4를 삭제합니다. 배열은 [2,9,1,4,2,3]이 되고, x는 5가 됩니다.
2. 다음으로 가장 오른쪽 요소 3을 삭제합니다. 배열은 [2,9,1,4,2]가 되고, x는 2가 됩니다.
3. 마지막으로 왼쪽(2)이나 오른쪽(2) 어느 쪽이든 하나를 더 삭제하면 x는 0이 되고, 배열은 [2,9,1,4] 또는 [9,1,4,2]가 됩니다.

풀이 접근 방식

이 문제의 핵심 아이디어는 접두사 합(prefix sum)과 접미사 합(suffix sum)을 활용하는 것입니다. 왼쪽에서 제거한 요소들의 누적 합을 미리 맵에 저장해 두고, 오른쪽에서 제거할 요소들의 합을 순회하면서 'x - 오른쪽 합'에 해당하는 값이 왼쪽 맵에 존재하는지 확인합니다. 이렇게 하면 전체를 탐색하지 않고도 O(n) 시간 복잡도로 답을 구할 수 있습니다.

이를 해결하기 위해 다음 단계를 따릅니다.

• n := nums의 크기
• leftMap := 새로운 맵(딕셔너리)
• leftMap[0] := -1
• left := 0
• i를 0부터 n-1까지 반복:
  • left := left + nums[i]
  • left가 leftMap에 없으면:
    • leftMap[left] := i
• right := 0
• ans := n + 1
• i를 n부터 0까지 1씩 감소시키며 반복:
  • i < n이면:
    • right := right + nums[i]
  • left := x - right
  • left가 leftMap에 있으면:
    • ans := ans와 leftMap[left] + 1 + n-i 중 최솟값
• ans가 n + 1과 같으면:
  • -1 반환
• ans 반환

구현 예제

아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.

def solve(nums, x):
   n = len(nums)

   leftMap = dict()
   leftMap[0] = -1
   left = 0
   for i in range(n):
      left += nums[i]
      if left not in leftMap:
         leftMap[left] = i

   right = 0
   ans = n + 1
   for i in range(n, -1, -1):
      if i < n:
         right += nums[i]
      left = x - right
      if left in leftMap:
         ans = min(ans, leftMap[left] + 1 + n - i)
   if ans == n + 1:
      return -1
   return ans

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

입력

[4,2,9,1,4,2,3], 9

출력

3