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

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

프로그래머스

ex) 

sequence =[1, 1, 1, 2, 3, 4, 5]

k = 5

1) 합이 k보다 작을 때 마다 end를 밀고 그 값을 더해준다.

값	1	1	1	2	3	4	5
	start - end
합	1

값	1	1	1	2	3	4	5
	start	end
합		2

값	1	1	1	2	3	4	5
	start		end
합			3

2) 합이 k와 같다면 {key = 인덱스 간의 차, value = start, end} 를 answer에 저장해 주고

값	1	1	1	2	3	4	5
	start			end
합				5

3) start의 값을 뺀 후 start를 민다.

값	1	1	1	2	3	4	5
		start		end
합				4

4) k보다 작아졌으니까 end한번 밀고, 더해주고

값	1	1	1	2	3	4	5
		start			end
합					7

5) 위에서 합은 k보다 크니까 start에 있는 값을 빼고 start를 밀어준다

값	1	1	1	2	3	4	5
			start		end
합					6

 

값	1	1	1	2	3	4	5
				start	end
합					5

6) 또 k니까 같은 방식으로 저장해주고, 빼주고, start를 민다.

값	1	1	1	2	3	4	5
					start - end
합					3

7) 반복...

정확성 테스트

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.07ms, 10.3MB)
테스트 4 〉	통과 (0.66ms, 10.2MB)
테스트 5 〉	통과 (8.49ms, 10.5MB)
테스트 6 〉	통과 (5.41ms, 10.7MB)
테스트 7 〉	통과 (18.17ms, 11.7MB)
테스트 8 〉	통과 (52.10ms, 13.3MB)
테스트 9 〉	통과 (82.11ms, 16.4MB)
테스트 10 〉	통과 (239.89ms, 26.5MB)
테스트 11 〉	통과 (387.88ms, 42.9MB)
테스트 12 〉	통과 (347.55ms, 43MB)
테스트 13 〉	통과 (395.90ms, 43.1MB)
테스트 14 〉	통과 (442.27ms, 43.2MB)
테스트 15 〉	통과 (495.12ms, 43.1MB)
테스트 16 〉	통과 (235.36ms, 51.3MB)
테스트 17 〉	통과 (622.50ms, 51.2MB)
테스트 18 〉	통과 (0.02ms, 10.3MB)
테스트 19 〉	통과 (0.01ms, 10.2MB)
테스트 20 〉	통과 (0.01ms, 10.1MB)
테스트 21 〉	통과 (0.01ms, 10.1MB)
테스트 22 〉	통과 (0.01ms, 10.1MB)
테스트 23 〉	통과 (0.01ms, 10.2MB)
테스트 24 〉	통과 (495.88ms, 18.6MB)
테스트 25 〉	통과 (215.24ms, 18.7MB)
테스트 26 〉	통과 (434.44ms, 18.6MB)
테스트 27 〉	통과 (368.73ms, 18.5MB)
테스트 28 〉	통과 (327.62ms, 18.5MB)
테스트 29 〉	통과 (300.20ms, 18.5MB)
테스트 30 〉	통과 (429.33ms, 51.3MB)
테스트 31 〉	통과 (0.01ms, 10.3MB)
테스트 32 〉	통과 (0.01ms, 10.1MB)
테스트 33 〉	통과 (0.01ms, 10.2MB)
테스트 34 〉	통과 (0.01ms, 10.2MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

 

 

def solution(sequence, k):
    answer_dic = dict()
    sum_result, start_index,end_index,answer_flag = sequence[0],0,0,False
    while start_index < len(sequence):
        if sum_result < k:
            end_index += 1
            if end_index >= len(sequence): break
            sum_result += sequence[end_index]
        elif sum_result > k or answer_flag == True:
            answer_flag = False
            sum_result -= sequence[start_index]
            start_index += 1
        else:
            if not end_index - start_index in answer_dic:
                answer_dic[end_index - start_index] = [start_index, end_index]
            answer_flag = True
    return answer_dic[min(answer_dic)]