(Python/LV2) 연속 부분 수열의 합

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/178870

풀이:

def solution(sequence, k):
    #left, right = 0, 1
    
    sum = 0
    end = 0
    res = []
    for i in range(len(sequence)):

        while sum < k and end < len(sequence):
            sum += sequence[end]
            end += 1
        if sum == k:
            res.append([ i,end-1,end-1-i ])
        sum -= sequence[i]
    res = sorted(res, key = lambda x:x[2])
    return res[0][:2]

 

저번주에 배웠던 투포인터 문제가 프로그래머스 2레벨 문제로 나와서 괜찮게 풀었다.

 

sum, end 를 0 으로 초기화

sequence 에 길이 만큼 돌면서

 

만약에 sum 이 k보다 작고, 끝 값이 len(sequence) 보다 작아야한다 그렇지 않으면 마지막 end 에서 에러난다.

 

그러면 총 합계를 올림과 동시에 end값도 같이 올려준다.

 

print(solution( [1, 1, 1, 2, 3, 4, 5], 5))

 

 

이걸로 예를들면

 

i가 0 일때 end 는 4 이고 sum 에는 시퀀스에 0부터 3까지 더해져있다,

그리고 k와 같으면 res에 [시작인덱스, 끝인덱스, 연속된 숫자의 개수]이다. 왜 end-1-i 인지 모른다면

 

만약 1 1 1 2 3 4 5 가 있다.

[1112] 말고 그 다음꺼인 [23] 으로 해보겠다

그러면 i 3이겠고 end에는 4가 와야하는데 while 문에서 sum을 해주고 1을 더했으니 -1 을 해주면 4가 나온다.

마지막인 end -1 - i 는

end가 4의 위치에서 i가 2 올때까지의 값이 i니깐 i를 빼주고 -1은 똑같다.

 

그리고 그 외는 sum에서 앞에 값이 i를 빼주고 다음 포문으로 넘어간다.

 

res 를 시작인덱스 기준으로 정렬