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

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

풀이

연속된 부분 수열의 합을 구해야 하기 때문에 L, R 인덱스에 접근해서 푸는 방식 선택

1. L과 R의 초기값 = 0, sum의 초기값 = 배열의 첫 번째 값

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

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

4. sum < k 이면 R값을 증가시킨 후 sum값에 R인덱스의 값 더함

5. sum > k 이면 sum값에 L인덱스 값을 뺀 후 L값을 증가

6. sum == k 이면 answer에 인덱스 저장
   !부분수열의 길이가 짧을 때를 도출해야 하므로 길이를 비교한 후 저장

예시)
sequence = [1, 1, 1, 2, 3, 4, 5], k = 5 인 경우

1 (0)	1 (1)	1 (2)	2 (3)	3 (4)	4 (5)	5 (6)	sum	answer
L R							1	[0,7]
L	R						2	[0,7]
L		R					3	[0,7]
L			R				5	[0,3]
	L		R				4	[0,3]
	L			R			7	[0,3]
		L		R			6	[0,3]
			L	R			5	[3,4]
				L R			3	[3,4]
				L	R		7	[3,4]
					L R		4	[3,4]
					L	R	9	[3,4]
						L R	5	[6,6]

---

코드

1. 통과한 코드

def solution(sequence, k):
    l = r = 0
    answer = [0, len(sequence)]
    sum = sequence[0]

    while True:
        if sum < k:
            r += 1
            if r == len(sequence): break
            sum += sequence[r]
        else:
            if sum == k:
                if r-l < answer[1]-answer[0]:
                    answer = [l, r]
            sum -= sequence[l]
            l += 1
    return answer

2. 시간 초과 코드 -> 매번 sum을 구해줘서 통과하지 못한 듯 싶음

def solution(sequence, k):
    l = r = 0
    answer = [0, len(sequence)]
    
    while l >= 0 and r <= len(sequence)+1:
        if sum(sequence[l:r]) < k:
            r += 1
        elif sum(sequence[l:r]) > k:
            l += 1
        else:
            if r-l < answer[1]-answer[0]-1:
                answer = [l, r-1]
            l += 1
    return answer