BOJ 1806. 부분합 (Python)

BOJ-1806. 부분합

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

1806번: 부분합

Solution

import sys

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

sum_untill_n = [0] * (N+1)
for i in range(1, N + 1):
    sum_untill_n[i] = sum_untill_n[i-1] + list[i-1]

min_length = sys.maxsize
start = 0
end = start + 1

while(start != N):
    if sum_untill_n[end] - sum_untill_n[start] >= S:
        min_length = min(end - start, min_length)
        start += 1

    else:
        if end != N:
            end += 1
        else:
            start += 1

if min_length == sys.maxsize:
    print(0)
else:
    print(min_length)

 

이건 LeetCode 3. Longest Substring Without Repeating Characters의 슬라이딩 기법을 연습하기 위해 푼 문제이다.

 

해결법을 생각해내는것은 비슷한 문제를 풀었기때문에 어려운 일은 아니였는데, 파이썬에 너무 익숙해졌나... 나태해진건가 sum()을 남발해서 시간초과가 계속 났다. sum()을 다른 코드로 대체하니 통과된것을 보니 분명하다.

 

sum()의 시간복잡도를 찾아보고 싶었는데 ㅜ 안나온다.

python wiki docs - 여기에도 없다.

직접 구해도 봤는데 ..

import time

# 1~10까지의 sum 구하기
list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# for loop sum
start_time = time.time()

sum_to_n = 0
for n in list:
    sum_to_n += n

print("for loop sum: ", time.time() - start_time)

# 파이썬 내장함수 sum()

start_time = time.time()

sum_to_n = sum(list)


"""
for loop sum:  0.0
sum():  0.0
"""

알 수가 없었다.. 할 수 있다면 내장함수를 남발하지 않도록 주의 해야겠다..

input()대신 sys.stdin을 사용하면 더 빠르게 풀이가 가능하다는데 내 경우에 input이 원인은 아닌 것 같다.