연속된 부분 수열의 합 (178870번) - 프로그래머스 (Programmers)

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

프로그래머스

 

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

 

난이도 : Lv 2

알고리즘 : Two Pointers (투 포인터)

Time Complexity : O( N )

 

def solution(seq, k):
    if seq[0] == k:
        return [0, 0]
    n = l = s = e = len(seq)
    i, j = 0, 1
    acc = seq[0]
    while i < j and j < n:
        if acc == k:
            if j-1-i < l:
                s, e = i, j-1
                l = e-s
            acc += seq[j]
            j += 1
            i += 2
            if j < i:
                return [s, e]
            acc -= seq[i-1] + seq[i-2]
        elif acc < k:
            acc += seq[j]
            j += 1
        else:
            acc -= seq[i]
            i += 1
    while i < j and k <= acc:
        if acc == k:
            if j-1-i < l:
                s, e = i, j-1
            return [s, e]
        acc -= seq[i]
        i += 1
    return [s, e]

 

오랜만에 투 포인터를 활용하는 문제였다.

 

1. 두 개의 포인터 i, j 를 모두 0으로 설정한다.

2-1. 현재 누적 합 acc가 k보다 작으면, j를 1 키워주고 acc에 sequence[j]를 더해준다.
2-2. acc가 k보다 크면, acc에 sequence[i]를 빼주고 i를 1 키워준다.
2-3. acc = k 이고, 현재 구간의 길이가 이전 acc = k 일 때의 구간 길이보다 작으면, 현재 i, j 를 기록해둔다.

3. 마지막에 기록된  i, j 를 출력한다.

 

위의 설명이 코드와 정확히 일치하지는 않지만,

대략 이런 느낌으로 풀면 된다.