[Programmers] 연속된 부분 수열의 합

문제

요약

수열에서 부분 수열의 합이 k와 같은 가장 짧은 구간, 짧은 구간이 여러개라면 가장 앞의 구간을 구해라.

 

원본

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

프로그래머스

풀이

풀이1(시간초과)

처음 생각한 풀이는 구간의 시작지점과 끝지점을

구간의 합이 k보다 클 경우, 같을 경우, 적을 경우로 구분해서 옮겨가는 것이다.

아쉽게도 테케 8개만 통과하고 시간초과가 발생한다.

시간복잡도 최악의 경우가 n^2 인가 보다.

def solution(sequence, k):
    s, e = 0, len(sequence)-1
    i, j = 0, 0
    
    while i < len(sequence) and j < len(sequence):
        t = sum(sequence[i:j+1])
        
        if t > k:
            i += 1
        elif t == k:
            if j - i < e-s:
                s, e = i, j
            j += 1
        else:
            j += 1
        
    return [s,e]

 

풀이2

시작 지점을 한바퀴 도는 것은 같으니까 for문으로 순회하면서 비교했다.

처음에 합과 끝지점인 m, e를 for문 안에서 정의해서 i부터 다시 비교했는데 그러면 똑같이 반복하게 되니까

시작지점을 옮겼을 때, 합했던 값에서 시작지점 값을 빼줬다.

def solution(sequence, k):
    n = len(sequence)
    m, e, l = 0, 0, n
    
    for i in range(n):
        while m < k and e < n:
            m += sequence[e]
            e += 1
        
        if m == k and l > e-1-i:
            answer = [i, e-1]
            l = e-1-i
        m -= sequence[i]
        
    return answer