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

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

 

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

프로그래머스

 

 

문제 설명

 

문제 및 입출력

• 주어진 수열의 경우 오름차순(비내림차순)으로 정렬이 되어있다.
• 이때 주어진 수열에서 주어진 수(k)를 만족하고 end-start의 크기가 최소인 start와 end를 반환하는 것이 목표

 

접근 방법

• start와 end를 기준으로 리스트를 탐색하며 start와 end 사이의 연속된 수의 합이 k가 되는지 확인
  • TwoPointer의 방법을 사용
    • 시간 복잡도는 O(N)이다
  • 변수 선언 
    • start, end, tot, temp 사용
• temp에 입력이 된 start, end, end-start의 리스트를 정렬
  • sort, key, lambda를 사용해서 정렬을 하며 이때 2번째 인덱스의 end-start의  오름차순으로 정렬
• return 값의 경우 temp [0][0], temp [0][1]로 하여 반환

 

문제 풀이

 

'''
인덱스의 값을 비교하는 방식으로 접근
필요 변수 : start, end, sum, temp
start, end, sum = 0,0, 0

while 반복문 종료조건 : end가 리스트의 크기를 넘어섰을 때 종료
sum =< k:
    같을 경우
        해당 start와 end의 값을 temp 추가
    해당 end +=1을 하여 sum에 [end]값 추가

sum > k:
    sum -= sq[start]
    start +=1 start의 값 조절


배열 정리
sort key lambda 사용으로 정렬
마지막의 경우 크기를 의미하므로 0,1번째 원소만 가져와서 반환
'''


def solution(sequence, k):
    answer = []
    start, end, tot = 0, 0, sequence[0]
    temp = []
    sequence += [k + 1]
    while end < len(sequence) - 1:
        if tot <= k:
            if tot == k:
                temp.append((start, end, end - start))
            end += 1
            tot += sequence[end]
        else:
            start += 1
            tot -= sequence[start - 1]

    temp.sort(key=lambda tot: tot[2])

    return temp[0][0], temp[0][1]