문제

링크

Code

def solution(sequence, k):
    s, e = 0, 1
    answer = []
    length = len(sequence)
    sums = [0 for _ in range(length+1)]
    sums[0] = 0
    for i in range(1, length+1):
        sums[i] = sums[i-1] + sequence[i-1]
    while s < e:
        if e > length:
            break
        elif (sums[e] - sums[s]) == k:
            d = e - s
            answer.append([d, s, e-1])
            s = e
            e = s + 1
        elif (sums[e] - sums[s]) > k:
            s += 1
        elif (sums[e] - sums[s]) < k:
            e += 1
    answer.sort()
    return [answer[0][1], answer[0][2]]

포인터만을 사용하도록 변경

def solution(sequence, k):
    s, e = 0, 0
    total = 0
    min_length = float('inf')
    answer = []

    while e < len(sequence):
        total += sequence[e]
        e += 1

        while total > k:
            total -= sequence[s]
            s += 1

        if total == k:
            if e - s < min_length:
                min_length = e - s
                answer = [s, e-1]

    return answer

소감

투포인터의 핵심은 상수 포인터 두 개를 사용하는 것이다.

그리고 k 값보다 크면 조금 줄여본다. 즉, 그래서 s를 1 증가시킨다.
만약 k보다 작다면, 크게 증가시켜본다. 즉, 그래서 e를 1 증가시킨다.

위의 전략을 따르지 않고 반대로 한다면, 초기 상태에서 아예 에러가 난다.
그리고 비오름차순으로 정렬되어 있다는 문제의 서술이 그리디하게 풀라는 신호로 해석될 수 있다.