Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

Python으로 길이 size의 연속 부분 리스트를 k번 증가시킨 후 최솟값 최대화하기

문제 개요

숫자로 이루어진 리스트 nums와 두 값 size, k가 주어진다고 가정해 봅시다. 사용할 수 있는 연산은 다음과 같습니다.

  • 길이가 정확히 size인 연속된 부분 리스트를 하나 선택한다.
  • 선택한 부분 리스트의 모든 요소를 1씩 증가시킨다.

이 연산을 최대 k번 수행할 수 있을 때, 리스트 전체에서 얻을 수 있는 최솟값의 최댓값을 구하는 것이 목표입니다.

예시

입력이 nums = [2, 5, 2, 2, 7], size = 3, k = 2라고 해보겠습니다.

  1. 첫 번째 연산으로 인덱스 0~2의 [2, 5, 2]를 증가시키면 [3, 6, 3, 2, 7]이 됩니다.
  2. 두 번째 연산으로 인덱스 1~3의 [6, 3, 2]를 증가시키면 [3, 7, 4, 3, 7]이 됩니다.

결과적으로 리스트의 최솟값은 3이 되며, 이것이 두 번의 연산으로 달성할 수 있는 최댓값입니다.

접근 방법: 이진 탐색 + 그리디

이 문제는 이진 탐색(Binary Search)과 그리디(Greedy) 기법을 결합하면 효율적으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다. "목표 최솟값 target을 k번 이내의 연산으로 달성할 수 있는가?"라는 질문은 단조성(monotonicity)을 가집니다. 즉, 어떤 target이 달성 가능하다면 그보다 작은 값도 반드시 달성 가능합니다. 따라서 답이 되는 target 값을 이진 탐색으로 찾을 수 있습니다.

달성 가능 여부는 왼쪽부터 차례로 확인하며 그리디하게 판단합니다. 각 위치에서 값이 target에 미치지 못하면, 현재 위치를 시작점으로 하는 부분 리스트에 필요한 만큼 연산을 적용하고, 차분 배열(diff array) 방식을 사용해 해당 연산이 끝나는 지점에 영향을 기록해 둡니다.

알고리즘 단계

  • possible(target) 함수를 정의합니다. target을 매개변수로 받아 k번 이내의 연산으로 달성 가능한지 판별합니다.
    • events := 크기가 N이고 0으로 초기화된 차분 배열
    • moves := 0, s := 0 (현재까지 누적된 증가량)
    • i를 0부터 N-1까지 순회하며:
      • s := s + events[i] — 종료된 연산 효과 제거
      • delta := target - (A[i] + s) — 부족한 만큼 계산
      • delta > 0이면:
        • moves += delta, s += delta
        • i + size < N이면 events[i + size] -= delta로 연산 종료 지점 기록
    • moves <= K이면 true 반환
  • 메인 로직에서는:
    • N := 리스트 A의 길이
    • left := 0, right := 10^10으로 탐색 범위 설정
    • left < right 동안:
      • mid := (left + right + 1) // 2
      • possible(mid)가 참이면 left := mid, 아니면 right := mid - 1
    • 최종적으로 left 반환

구현 코드

아래는 위 알고리즘을 Python으로 구현한 전체 코드입니다.

class Solution:
    def solve(self, A, size, K):
        N = len(A)

        def possible(target):
            events = [0] * N
            moves = s = 0
            for i in range(N):
                s += events[i]
                delta = target - (A[i] + s)
                if delta > 0:
                    moves += delta
                    s += delta
                    if i + size < N:
                        events[i + size] -= delta
            return moves <= K

        left, right = 0, 10 ** 10
        while left < right:
            mid = (left + right + 1) // 2
            if possible(mid):
                left = mid
            else:
                right = mid - 1
        return left

ob = Solution()
nums = [2, 5, 2, 2, 7]
size = 3
k = 2
print(ob.solve(nums, size, k))

실행 결과

입력

[2, 5, 2, 2, 7], 3, 2

출력

3

복잡도 분석

  • 시간 복잡도: O(N log M) — N은 리스트 길이, M은 탐색 범위(10^10)입니다. 각 이진 탐색 단계마다 possible() 함수가 O(N) 시간에 실행됩니다.
  • 공간 복잡도: O(N) — 차분 배열 events를 저장하는 데 필요합니다.

차분 배열을 활용하면 각 연산의 시작과 끝만 기록하므로, 실제로 부분 리스트를 일일이 갱신하지 않고도 누적 증가량을 O(1)에 처리할 수 있다는 점이 이 풀이의 핵심입니다.