백준 1806 부분합 (파이썬)

문제 : https://www.acmicpc.net/problem/1806

첫번째 제출 코드 (시간초과)

import sys

def solve():
    start = 0
    end = 0
    answer = N+1

    while end < N:
        if sum(numbers[start:end+1]) >= S:
            if answer > (end+1 - start):
                answer = (end+1 - start)
            start += 1
            if start > end:
                end += 1
                start -= 1

        else:
            end += 1
    
    if answer == N+1:
        print(0)
        
    else:
        print(answer)
    return

if __name__ == "__main__":
    input = sys.stdin.readline
    N, S = map(int, input().split())
    numbers = list(map(int, input().split()))
    solve()

매 번 sum으로 합을 확인해서 시간초과가 발생했습니다.

sum함수의 시간 복잡도가 O(N)이므로 위 코드를 투 포인터로 풀어도 O(N^2)으로 최대 O(10^10)이 나옵니다.

따라서 sum을 사용하지 않고 두번째 방법으로 문제를 해결했습니다

 

두번째 제출 코드 (정답)

import sys

def solve():
    start = 0
    end = 0
    answer = N+1
    temp = numbers[0]
    while end < N:
        if temp >= S:
            if answer > (end + 1 - start):
                answer = (end + 1 - start)
            temp -= numbers[start]
            start += 1
            if start > end:
                end += 1
                if end >= N:
                    break
                start -= 1
                temp += numbers[end]
        elif temp < S:
            end += 1
            if end >= N:
                break
            temp += numbers[end]


    if answer == N+1:
        answer = 0
    print(answer)
    return

if __name__ == "__main__":
    input = sys.stdin.readline
    N, S = map(int, input().split())
    numbers = list(map(int, input().split()))
    solve()

start + 1을 할 경우 start-1 부분을 빼주고 end + 1 을 할 경우 end + 1 부분을 더해주었습니다.

위 경우만 계산하니 시간 복잡도를 O(N)으로 크게 줄일 수 있었습니다.