[BOJ]1806. 부분합

문제

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

 

 

사용 알고리즘

투 포인터, 누적 합

 

풀이

고려사항

1. 시간 제한이 까다로운 문제

 

후기

1. Brute Force

가능한 부분 수열 모두를 탐색하는 방식으로 접근했다.

시간 복잡도는 O(N2)이다.

이때, N의 범위가 10 ≤ N < 100,000 으로 시간초과가 발생했다.

N이 매우 클 때 시간 초과가 발생할 수 있는 코드이다.

## 시간 초과 코드 - Brute Force ##

import sys

input = sys.stdin.readline


def find(num_list):
    for l in range(1, len(num_list) + 1):
        for i in range(len(num_list) - l):
            if sum(num_list[i : i + l]) == S:
                return l
    return 0


N, S = map(int, input().split())

num_list = list(map(int, input().split()))
print(find(num_list))

 

2. 투 포인터 (Two Pointer) 방식

위의 방식이 시간 초과가 발생하였기 때문에 시간적 효율을 높이기 위해 투 포인터를 채택했다.

투 포인터를 사용하면 한 번의 진행으로 문제 해결이 가능하고 시간 복잡도는 O(N)이다.

N이 커도 투 포인터로 배열을 한 번만 스캔하기 때문에 시간적 측면에서 효율적이다.

 

코드

## 투 포인터 코드 ##

import sys

input = sys.stdin.readline

N, S = map(int, input().split())
num_list = list(map(int, input().split()))

left, right = 0, 0
sum = 0
min_length = 1e9

while True:
    if sum >= S:
        min_length = min(min_length, right - left)
        sum -= num_list[left]
        left += 1
    elif right == N:
        break
    else:
        sum += num_list[right]
        right += 1

if min_length == 1e9:
    print(0)
else:
    print(min_length)

 

결과