이번 글에서는 배열과 두 개의 값 limit, goal이 주어졌을 때, 배열의 합이 goal과 같아지도록 하기 위해 최소 몇 개의 요소를 추가해야 하는지 구하는 방법을 알아보겠습니다.
문제 설명
배열 nums가 있고, 이 배열은 특별한 조건을 가집니다. 즉, 모든 인덱스 i에 대해 |nums[i]| <= limit이 성립합니다. 우리는 배열의 합을 goal과 동일하게 만들기 위해 삽입해야 하는 요소의 최소 개수를 찾아야 하며, 이때 추가하는 요소 역시 limit 값을 초과해서는 안 됩니다.
예를 들어, 입력이 nums = [2, -2, 2], limit = 3, goal = -4라고 가정해 봅시다. 이 경우 출력값은 2가 됩니다. 왜냐하면 -3을 두 번 추가하여 배열을 [2, -2, 2, -3, -3]로 만들면 합이 -4가 되기 때문입니다.
해결 접근 방식
이 문제는 간단한 수학적 계산으로 해결할 수 있습니다. 단계는 다음과 같습니다.
- 먼저 nums 배열의 모든 요소의 합을 계산합니다. 이를 s라고 합시다.
- 목표값과 현재 합의 차이의 절댓값을 구합니다. 즉, ab = |goal − s| 입니다.
- 마지막으로 ab를 limit으로 나눈 값의 올림(ceiling)을 반환합니다. 이것이 곧 추가해야 할 최소 요소 개수입니다.
구현 예제
아래 코드를 통해 더 자세히 이해해 보겠습니다.
from math import ceil def solve(nums, limit, goal): s = sum(nums) ab = abs(goal - s) return ceil(ab / limit) nums = [2, -2, 2] limit = 3 goal = -4 print(solve(nums, limit, goal))
입력
[2, -2, 2], 3, -4
출력
2.0
동작 원리 살펴보기
위 예제에서 현재 배열의 합은 2 + (-2) + 2 = 2입니다. 목표값인 -4와의 차이는 |-4 − 2| = 6입니다. limit이 3이므로 한 번에 최대 3만큼씩 줄일 수 있고, 6 ÷ 3 = 2가 되어 정확히 2개의 요소만 추가하면 됩니다.
여기서 올림 함수(ceil)를 사용하는 이유는, 차이가 limit으로 나누어떨어지지 않는 경우에도 필요한 만큼의 요소를 모두 추가할 수 있도록 하기 위함입니다. 예를 들어 차이가 7이고 limit이 3이라면, 7 ÷ 3 ≈ 2.33이지만 실제로는 3개의 요소가 필요합니다.
이 알고리즘의 시간 복잡도는 배열의 합을 계산하는 데 O(n), 나머지 연산은 상수 시간이 걸리므로 전체적으로 O(n)입니다.