[ 프로그래머스 / LV2 / 파이썬 Python ] 연속된 부분 수열의 합

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

프로그래머스

 

코드

---

def solution(sequence, k):
    answer = []
    n = len(sequence)
    s,end = 0, 0
    for i in range(len(sequence)):
        while s < k and end < n:
            s += sequence[end]
            end += 1
        if s == k:
            answer.append((i,end-1))
        s -= sequence[i]
            
    return sorted(answer,key=lambda x: x[1]-x[0])[0]

 

풀이

---

아직 투포인터에서 start와 end를 다루는 기준을 정확하게 정하지 못하고 있다. 조금 더 풀어봐야 한다.

 

문제를 읽어보았다면 연속된 부분수열을 찾는 것이기 때문에 투포인터를 사용해서 풀어야 한다는 것을 눈치챘을 것이다.

 

처음 시도할 때는 매번 합을 구하는 시간을 줄이기 위해 누적합을 사용하였다. 근데 누적합에서는 첫 번째 인덱스가 포함되지 않는다는 문제가 있었다.

예시를 들어보자면, 1 2 3의 누적합은 1 3 6 이다. 

1 3 6을 순차적으로 탐색하면서 구할 수 있는 부분합은 (3-1), (6-1), (6-3) 이다. 이러면 첫 번쨰 원소를 포함한 부분수열을 구할 수가 없다. 물론 누적합의 인덱스를 하나씩 미뤄서 0 1 3 6 이런 형식으로 사용하면 할 수 있지만 마음에 들지 않아서 누적합을 포기하였다.

따라서 누적합 없이 매번 합을 갱신해주기로 했다.

 

이 문제에서 내가 가장 핵심이라고 생각하는 부분은 비내림차순==오름차순으로 정렬이 되어 있다는 것이다.

정렬이 되어 있기 때문에 투포인터에서 인덱스가 앞으로 다시 돌아가야 할 일은 없다. left와 right가 있을 때, 둘 다 커지는 방향으로 나아가고 줄어드는 방향으로 갈 일은 없다는 것이다.

 

이 한 가지 개념으로도 이 문제는 쉽게 해결할 수 있다.

현재 위치에서 k보다 부분합이 커질 때까지 계속해서 탐색을 이어나가고 k와 같아진다면 answer에 저장한다.

다음 인덱스로 넘어가서 탐색할 때에도 end의 위치는 바뀔 필요가 없다. 왜냐하면 start인덱스가 커짐으로써 부분합의 크기가 줄어들기 때문이다. 여기서 end를 줄인다고 k와 같아질 가능성이 없다는 말이다.

따라서 start(i)인덱스만 움직이면서 k와 부분합이 같은지만 검사하고 마지막에 answer를 수열의 길이 -> 시작인덱스 순으로 정렬하여 첫 원소를 반환하면 된다.