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

출처 : 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/178870

프로그래머스

 

# 비내림차순 정렬(점점 증가하는 수열)이 주어질 때

# 시작idx와 길이가 가장 작으면서 내부 요소 총합이 k인 부분 수열의 [시작 idx, 끝 idx]를 return

 

 

먼저, 생각해야 할 부분

 

1. 조합으로 풀기에는 sequence가 1,000,000개까지 존재할 수도 있다.

     수열의 부분합을 빠르게 구할 수 있는 다른 방법은 무엇이 있을까?

---

 

Two Pointer를 이용한 풀이

 

# 합이 k보다 작으면, 뒤의 한 칸을 추가해 길이를 늘린다.
# 합이 k보다 크면, 앞의 한 칸을 제거해 길이를 줄인다.
# 이를 배열 끝까지 반복한다. -> 가장 작은 길이를 계속 업데이트

 

def solution(sequence, k):
    ans_p1 = 0
    ans_p2 = len(sequence) + 1
    
    # p1부터 p2까지
    p1 = 0
    p2 = 0
    
    array_sum = sequence[0]
  
    while p1 < len(sequence) and p2 < len(sequence):
        if array_sum < k:
            p2 += 1
            if p2 < len(sequence):
                array_sum += sequence[p2]
        elif array_sum > k:
            array_sum -= sequence[p1]
            p1 += 1
        else: # array_sum == k
            min_length = ans_p2 - ans_p1 + 1
            current_length = p2 - p1 + 1

            if current_length < min_length:
                ans_p1 = p1
                ans_p2 = p2

            p2 += 1
            if p2 < len(sequence):
                array_sum += sequence[p2]

    return [ans_p1, ans_p2]

 

---

고찰

 

배열의 부분합을 구할 때는 투 포인터를 생각해보자.

 

Github

GitHub - bh2980/Algorithm-Problem: 알고리즘 풀이 흔적들