[프로그래머스] Python Level2 연습문제 - 연속된 부분 수열의 합

문제 바로가기

접근 방법

일반적인 탐색은 시간 초과가 난다. 다른 방법이 필요하다.

1. 두 개의 포인터를 이용해야 한다.
2. 앞쪽 포인터는 그대로 두고 뒤쪽 포인터를 이동하여 누적 합을 계산해 준다.
3. 누적합이 k와 같을 때까지 뒤쪽 포인터를 이동한다.
4. 만약 누적합이 k와 같다면 가장 작은 인덱스를 구해야 한다.
   -> 가장 작은 인덱스를 저장해 놓는다.;
5. 만약 누적합이 k보다 크다면 값들을 덜어내야 한다. 앞쪽 포인터의 값을 k보다 작을 때까지 덜어내고 앞쪽 포인터를 이동 시킨다.

코드

def solution(sequence, k):
    answer = []
    
    # k가 배열 안에 있다면 바로 리턴하여 종료
    if k in sequence:
        return [sequence.index(k), sequence.index(k)]

    sumN = 0
    start, end = 0, 0
    minIndex = 1e9
    
    while len(sequence) != end:
    	# 뒤쪽 포인터를 이동하며 누적합
        sumN += sequence[end]
        end += 1

        if sumN > k:
            while sumN > k:
               sumN -= sequence[start]
               # 앞쪽 포인터 이동
               start += 1

        if sumN == k:
        	# 가장 작은 인덱스 저장
            if minIndex > (end - start - 1):
                minIndex = (end - start - 1)
                # 뒤쪽 포인터는 이미 움직였기 때문에 1을 빼줘야 한다.
                answer = [start, end - 1]

    return answer