[Programmers] #181884 - n보다 커질 때까지 더하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

배열을 앞에서부터 순회하며 누적합을 갱신하고, 누적합이 n을 처음으로 초과하는 순간 그 값을 반환한다. n이 전체 원소의 합보다 작다고 보장되므로 순회가 끝나기 전에 반드시 조건을 만족하는 시점이 나온다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(1)$

($N$ = numbers의 길이)

---

3. 코드

풀이 [Java][C++][Python]

class Solution {
    public int solution(int[] numbers, int n) {
        int sum = 0;
        for (int x : numbers) {
            sum += x;
            if (sum > n) return sum;
        }

        return -1;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> numbers, int n) {
    int sum = 0;
    for (int x : numbers) {
        sum += x;
        if (sum > n) return sum;
    }

    return -1;
}

from itertools import accumulate


def solution(numbers, n):
    return next(s for s in accumulate(numbers) if s > n)

accumulate(numbers)는 앞에서부터의 누적합을 하나씩 지연 생성하는 이터레이터다. 제너레이터 표현식으로 n을 초과하는 첫 값만 통과시키고 next로 그 값을 꺼내므로, 조건을 만족하는 누적합이 나오는 순간 순회가 멈추고 남은 원소는 더하지 않는다.

---