[구현] 연속된 부분 수열의 합 (투포인터에 대해서...)

문제

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

시행착오

맨 처음에 이중 for문을 사용해서 완전 탐색으로 찾으려고 했다. sequence[0]부터 끝까지 탐색, 다시 sequence[1]부터 끝까지 탐색.. 이렇게 하려고 했다.
그러면 시간초과 (sequence최대 배열 길이가 100만이니까 이중 for문을 쓰면 10억을 훨씬 넘어간다. 
이코테에서 연산 횟수가 10억을 넘어가면 c언어를 기준으로 1초를 넘어가니까 파이썬은 더 오래걸리겠지..? 
그래서 문제에 나와있는 '비내림차순' 이라는 조건을 활용해서 O(n)으로 풀어보자했다.

 

근데 전혀 방법이 생각이 나질 않아서 프로그래머스에 질문목록을 참고했고 아래 코드를 보았다

def solution(sequence, k):
    num = 0
    for i in range(len(sequence)-1, -1, -1):
        num += sequence[i]
        if num > k:
            num -= sequence.pop() 
        if num == k:
            while sequence[i-1] == sequence[-1] and i>0:
                i-=1
                sequence.pop()

            return [i, len(sequence)-1]

위 코드의 접근 방식은 아래와 같다

조건 1.
비내림차순 배열이니 iteration을 역으로 돌리면 최초로 찾는 연속합 =k 가 최소 원소 갯수에 부합합니다. 추가 탐색 불필요

조건 2.
조건 1을 만족하며 index가 더 낮은 경우만 찾으면 되겠네요. 예를 들어 ([2,2,2,2,2], 4) 같이... 조금만 생각해보면 연속합을 구성하는 숫자들이 다르다면 index를 낮췄을 때 연속합 =k 의 원소 갯수가 늘어날 수 밖에 없습니다. 즉 동일한 숫자가 반복되는 경우만 고려하면 쉽게 해결 가능 합니다.

 

어찌저찌 코드를 이해하긴 했는데 확 와닿지 않는 느낌이라 구글링해서 다른 풀이를 찾아보았다

투포인터를 이용하라는 글을 보니까 이해가 바로 되었다.

 

투포인터란

일단 투포인터 개념을 알아보자

리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘

 

start와 end 포인터를 가지고 리스트를 탐색하는 것이다. 매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고 각 포인터가 n번 누적 증가해야 알고리즘이 끝난다.

즉 시간 복잡도는 O(N)이다.

 

투포인터로 문제 풀이

이 개념을 가지고 문제를 해결해보자

1. start, end 포인터를 sequence의 인덱스 0을 가리키게 한다.
2. end를 1씩 늘리면서 sequence[start] ~ sequence[end]까지의 누적합을 구하다가 누적합이 k보다 커지면 start에 1을 더하고 다시 누적합을 구한다
3. k와 누적합이 같아지는 순간의 interval을 구해주고 기존 interval과 비교해서 더 짧은 것을 저장해준다 (길이가 짧은 수열 구하기), 이때 start와 end 인덱스를 저장해준다.

 

위와 같이 알고리즘을 설계하면 O(N)으로 풀이할 수 있다.

코드는 아래와 같다

 

def solution(sequence, k):
    answer = []
    end = 0
    n = len(sequence)
    invertal = n
    idx = []
    sum = 0
    for start in range(len(sequence)):
        while sum < k and end < n:
            sum += sequence[end]
            end += 1
        #k==sum을 만족했을 때 요소길이 비교
        if sum == k and invertal > end-1-start:
            #최소 인덱스 저장
            idx = [start, end-1]
            invertal = end-1-start
        sum -= sequence[start]

    return idx