[프로그래머스] 연습문제(LV2) : 연속된 부분 수열의 합

<문제출처>

https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

부분 수열의 합이 k인 부분수열의 구간을 구하여라. 길이가 더 짧고, 구간이 더 앞쪽에있는 정답을 찾자.

 

<고민 끄적끄적>

sequence(≤ 1,000,000) 이므로 구간의 합을 1번의 for문을 통해 구해야 한다.

구간합을 O(N)에 구하기 위해 누적합을 구한다.

투포인터(p1, p2)를 활용해서 앞에서부터 k값에 해당하는 구간을 찾는다.
현재 구간합이 k보다 작으면 p2를 늘려주고, k보다 크다면 p1을 늘려주는 방식으로 해결

합이 k인 구간이 여러개 있을 수 있고, 여러개 있다면 index가 빠른 구간을 정답으로 처리해야 하기 때문에, 구간을 순회하면서 정답 index와 구간의 최솟값을 기록하며 갱신한다.

 

 

최종코드

import sys

def interval_sum(s, e, prefix_sum):
    if s == 0:
        return prefix_sum[e]
    return prefix_sum[e] - prefix_sum[s - 1]
    
    
def solution(sequence, k):

    # 누적합 만들기
    n = len(sequence)
    prefix_sum = []
    
    prefix_sum.append(sequence[0])
    for i in range(1, n):
        prefix_sum.append(prefix_sum[-1] + sequence[i])
        
    
    MAX_SIZE = sys.maxsize
    answer = [0, MAX_SIZE]
    s, e = 0, 0
    while s <= e and s < n and e < n:
        v = interval_sum(s, e, prefix_sum)
        
        if v == k:
            if (e - s) < answer[1] - answer[0]:
                answer[0], answer[1] = s, e
        
        if v > k:
            s += 1
        elif v <= k:
            e += 1
            
    return answer