[알고리즘] 프로그래머스 Lv2 연속된 부분 수열의 합

문제

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

코드 구상

처음

완전 탐색으로 일단 풀어볼까? + sort 사용
-> 예시 테스트 케이스는 맞으나 1-5번 빼고 모두 시간초과

def solution(seq, k):
    idx_list = []

    MIN = len(seq)
    for i in range(len(seq)):
        SUM = 0
        j = i
        while SUM < k and j < len(seq) and (j-i) <= MIN:
            SUM += seq[j]
            j += 1
            if SUM > k:
                break

        if SUM == k:
            j -= 1
            idx_list.append([j-i, i, j])
            MIN = min(j-i, MIN)

    idx_list.sort(key=lambda x: (len(x), x[0]))
    # print(idx_list)
    answer = [idx_list[0][1], idx_list[0][2]]
    return answer

다음 단계

최소힙 개념을 적용해볼까? (길이가 가장 짧은 인덱스 짝이 가장 앞에 위치하도록)
그럼 sort를 안해도 되니까!
-> 1-5번 빼고 모두 시간초과

import heapq

def solution(seq, k):
    idx_heap = []

    MIN = len(seq)
    for i in range(len(seq)):
        SUM = 0
        j = i
        while SUM < k and j < len(seq) and (j-i) <= MIN:
            SUM += seq[j]
            j += 1
            if SUM > k:
                break

        if SUM == k:
            j -= 1
            heapq.heappush(idx_heap, [j-i, i, j])
            MIN = min(j-i, MIN)

    answer = heapq.heappop(idx_heap)
    return answer

[질문하기]를 뒤져본 후

이 글에서 얘기한 접근 방법이 풀이를 생각하는게 굉장히 큰 도움이 되었음

• 부분수열의 부분수열을 만들어서 확인
• 선형시간(O(N)) 안에 풀어야 한다는 점

풀이 코드

def solution(seq, k):
    if k in seq:
        return [seq.index(k), seq.index(k)]
    SUM = 0
    start = 0
    MIN = len(seq)
    answer = False
    for i in range(len(seq)):
        if SUM == k:
            if (i - start - 1) < MIN:
                answer = [start, i-1]
                MIN = i - start - 1

        SUM += seq[i]
        if SUM < k:
            continue

        while SUM > k:
            SUM -= seq[start]
            start += 1

    if not answer and SUM == k:
        answer = [start, len(seq)-1]

    return answer

힌트를 얻은 곳

https://school.programmers.co.kr/questions/47009
https://school.programmers.co.kr/questions/47019 (첫번째 반례만 참고)