배열 nums가 주어졌다고 가정해 봅시다. 한 번의 연산으로 배열에서 원소 하나를 선택해 그 값을 1만큼 증가시킬 수 있습니다. 예를 들어 [4, 5, 6]이 있을 때 인덱스 1의 원소를 선택하면 배열은 [4, 6, 6]이 됩니다. 목표는 nums를 엄격하게 증가(strictly increasing)하는 배열로 만들기 위해 필요한 최소 연산 횟수를 구하는 것입니다.
예를 들어 입력이 nums = [8, 5, 7]이라면 출력은 7이 됩니다. 다음 순서대로 원소를 증가시켜야 하기 때문입니다.
[8, 6, 7] → [8, 7, 7] → [8, 8, 7] → [8, 9, 7] → [8, 9, 8] → [8, 9, 9] → [8, 9, 10]
문제 해결 접근 방법
이 문제는 그리디(greedy) 방식으로 해결할 수 있습니다. 배열을 왼쪽에서 오른쪽으로 한 번만 훑으면서 인접한 두 원소를 비교하고, 증가 조건을 어기는 경우 즉시 값을 보정합니다.
count를 0으로 초기화합니다.i를 0부터 (배열 길이 − 2)까지 반복하며 다음을 수행합니다.만약
nums[i+1] ≤ nums[i]라면:count에nums[i] − nums[i+1] + 1을 더합니다.nums[i+1]을nums[i] + 1로 갱신합니다.
반복이 끝나면
count를 반환합니다.
구현 예제
def solve(nums):
count = 0
for i in range(len(nums) - 1):
if nums[i + 1] <= nums[i]:
count += nums[i] - nums[i + 1] + 1
nums[i + 1] = nums[i] + 1
return count
nums = [8, 5, 7]
print(solve(nums))입력
[8, 5, 7]
출력
7
동작 원리 상세 설명
핵심 아이디어는 간단합니다. 어떤 원소가 바로 앞의 원소보다 작거나 같다면, 두 값의 차이에 1을 더한 만큼의 연산이 반드시 필요합니다. 예를 들어 앞의 값이 8이고 뒤의 값이 5라면, 뒤의 값을 최소 9로 만들어야 하므로 8 − 5 + 1 = 4번의 연산이 필요합니다. 연산 횟수를 누적한 뒤 해당 원소를 9로 갱신하면, 이후 단계의 비교에서도 항상 올바른 기준값이 사용됩니다.
이 알고리즘은 배열 전체를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)로 매우 효율적입니다.