[프로그래머스]Lv2. 연속된 부분 수열의 합(Python)

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

프로그래머스

 

문제 접근

 

L과 R을 이동시키며 그 사이의 합(sum)을 담고 L과 R의 인덱스 값을 answer에 담는다.

 

1. L, R(인덱스)의 초기값 = 0

     sum의 초기값 = 배열의 첫 번째 값

     answer의 초기값 = [0, 배열의 길이]

2. sum = L부터 R까지의 합 

3. sum < k이면 R값을 증가시키고 sum에 R의 인덱스의 값 누적

4. sum > k이면 sum에 L의 인덱스의 값 빼고 L인덱스를 증가

5. sum == k이면 answer에 인덱스 값 저장 후 리턴 

 

코드

def solution(sequence, k):
    answer = []
    
    # 초기값 설정 
    l = r = 0   # 인덱스임
    answer = [0, len(sequence)]
    sum = sequence[0]
    
    while True:
        if sum < k:
            r += 1  # r의 인덱스 값을 증가 
            if r == len(sequence):  # sequence 길이 초과하면 break
                break
            sum += sequence[r]
        else:   # sum >= k이면 
            if sum == k:    # 현재 구간의 합이 k와 같다면
                if r-l < answer[1]-answer[0]:   # 현재 구간의 길이가 answer에 저장된 구간의 길이보다 작은 경우
                    answer = [l, r]
            sum -= sequence[l]  # l의 인덱스의 값을 sum에서 빼줌
            l += 1  # l의 인덱스 값을 증가
            
    return answer

 

문제 회고

 

두 개의 포인터(인덱스 l, r)을 두고 k보다 작은 때는 r의 인덱스를 증가시켜 범위를 확장시키고(단 sequence의 길이를 초과하면 안 됨) 그리고 k보다 클 때는 l의 인덱스를 하나 증가시켜 범위를 줄이고 sum에서 빼주는 과정을 반복한다. 하지만 sum == k를 만족시키는 여러 경우가 있기에 만약 answer에 저장되어 있는 answer의 길이가 현재 구간의 길이보다 크면 더 작은 값으로 갱신해 주는 과정이 필요하다.