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

문제 출처

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

프로그래머스

 

 

문제 풀이

이제 "부분 합"이라는 단어가 나오면 자동적으로 'right까지의 합 - left까지의 합'을 떠올린다. 확실히 매번 합을 구하는 것보다, 먼저 i까지의 합을 계산하고 뺄셈을 이용하는 방식이 효율적이다. 

 

해당 문제는 부분 합이 k가 되는 부분을 찾는 문제이다. 풀이는 간단하다. left, right를 0,0으로 두고 앞서말한 'right까지의 합 - left까지의 합'를 계산한다. 그 값이 k보다 작다면 right를 증가시키고, 크다면 left를 증가시키면 된다. 해당 아이디어만 가지고 있다면 문제 푸는 데 큰 어려움은 없을 것이다.

 

 

반복문 조건은 'right, left이 n보다 작다' 일 것이다. 하지만 right, left 증가 후에 바로 sequence 인덱싱으로 값을 가져오기에 인덱스가 n일 경우 out of range 에러가 발생한다. 따라서 그 사이에 if문으로 break를 넣어야 했다. 코드가 너무 못생겨져서 차라리 sequence에 1개를 append해서 보기 편하도록 작성했다. out of range 에러 문제를 해결했다.

 

또한, 사전에 합들을 전부 계산해도 된다. 하지만 필자는 뒤에 left, right 증가시키면서 반복하는 과정이 들어가기에, 사전에 계산하는 게 비효율적이라고 생각했다. 따라서 left, right 증가시키며 합을 계산했다.

 

 

 

코드에 주석을 달아놓았다!