[프로그래머스][누적합] 연속된 부분 수열의 합

연속된 부분 수열의 합

프로그래머스

 

• 내 풀이
  • 누적 합 (Prefix Sum)
    • prefix_sum[i] = prefix_sum[i-1] + sequence[i-1]
    • 구간 합 계산: prefix_sum[r] - prefix_sum[l]
      • prefix_sum[l]부터 prefix_sum[r]까지의 합은 수열의 l+1부터 r까지의 합.
  • 이진 탐색 (bisect_left)
    • r = bisect_left(prefix_sum, k)
      • prefix_sum에서 k 이상인 첫 번째 인덱스를 찾음.
  • 투 포인터 방식 탐색
    • 투 포인터 (l, r): l은 구간의 시작, r은 구간의 끝을 나타냄.
    • prefix_sum[r] - prefix_sum[l] == k일 때, 해당 구간의 길이와 시작 인덱스를 tmp에 기록.
      • 구간 길이: r - l
      • 시작 인덱스: l
    • 길이가 짧은 구간을 우선 선택하고, 길이가 동일하면 시작 인덱스가 더 작은 구간을 선택.
  • 구간 길이와 첫 번째 값 저장
    • 최소 길이를 찾으면서 동시에 해당 구간의 시작 인덱스 값도 함께 저장하여 비교.

from bisect import bisect_left

def solution(sequence, k):
    tmp=[float('inf'),float('inf')]
    answer=[]
    
    n=len(sequence)
    sequence=[0]+sequence
    prefix_sum=[0 for _ in range(n+1)]
    
    for i in range(1,n+1):
        prefix_sum[i]=prefix_sum[i-1]+sequence[i]
    
    idx=bisect_left(prefix_sum, k)
    l,r=0,idx
    
    while r<=n and l<r:
        if prefix_sum[r]-prefix_sum[l]==k:
            if r-l==tmp[0]:
                if l<tmp[1]:
                    tmp[1]=sequence[l]
            elif r-l<tmp[0]:
                tmp[0]=r-l
                tmp[1]=l
            l+=1
        elif prefix_sum[r]-prefix_sum[l]>k:
            l+=1
        else:
            r+=1
    
    answer.append(tmp[1])
    answer.append(tmp[1]+tmp[0]-1)
    return answer