BOJ 1806. 부분합 (Python)
2021. 1. 25. 12:19ㆍProblem Solving/BOJ
BOJ-1806. 부분합
https://www.acmicpc.net/problem/1806
1806번: 부분합
첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
www.acmicpc.net
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이 원인은 아닌 것 같다.
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
BOJ 2675. 문자열 반복 (Python) (0) | 2021.02.05 |
---|---|
BOJ 2667. 단지 번호 붙이기 (Python) (0) | 2021.01.27 |
BOJ 10951. A+B - 4 (C/C++) (0) | 2020.09.04 |
BOJ 10950. A+B - 3 (C/C++) (0) | 2020.09.04 |
BOJ 10789. 세로읽기 (C/C++) (0) | 2020.07.15 |