[투포인터] (프로그래머스_178870) 연속된 부분 수열의 합

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

 

📌 틀렸던 이유:

✅ 초기화 부분을 start,end=0,0으로해야하는데 start<end 이렇게 생각해서 0,1로 초기화했음

(합의 조건이 무조건 두개이상의 원소는 아님)

✅ sum_value를 먼저 정해주고 while을 돌려야 정확하게 조건에서 걸리는데 while문 이후에 정해줘서 로직이 꼬였음

 

📌 알고리즘:

1️⃣  start_idx, end_idx, sum_value=0,0,0으로 초기화해준다.

마지막에 가장 길이가 짧은 수열의 처음,시작 인덱스를 반환해야하므로 

힙을 활용한다.

from heapq import heappop,heappush
def solution(sequence, k):
    start_idx,end_idx=0,0
    sum_value=0
    hq = []

 

2️⃣  end_idx를 for문으로 증가시킨다. 그리고 sum_value값을 그에 따라 갱신한다.

만약 sum_value가 k보다 크면 start_idx가 end_idx랑 동일해지는 조건 안에서

sum_value에서 이전 start_idx값을 빼주고 start_idx를 증가시킨다.

    for end_idx in range(len(sequence)):
        sum_value+=sequence[end_idx]
        while sum_value>k and start_idx<=end_idx:
            sum_value-=sequence[start_idx]
            start_idx+=1

 

3️⃣ 만약 while문을 빠져나왔을 때의 sum_value가 k값과 동일하다면 힙에 담는다.

        if sum_value==k:
            heappush(hq,[end_idx-start_idx,[start_idx,end_idx]])

 

4️⃣ for문을 다 돌고 난 후 힙에서 원소를 꺼낸다.

    return heappop(hq)[1]

 

📌 전체 코드

from heapq import heappop,heappush
def solution(sequence, k):
    start_idx,end_idx=0,0
    sum_value=0
    hq = []
    for end_idx in range(len(sequence)):
        sum_value+=sequence[end_idx]
        while sum_value>k and start_idx<=end_idx:
            sum_value-=sequence[start_idx]
            start_idx+=1
        if sum_value==k:
            heappush(hq,[end_idx-start_idx,[start_idx,end_idx]])

    return heappop(hq)[1]