[백준/Python] 11659번 구간 합 구하기 4

---

문제

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

---

문제풀이(시간초과1)

처음에 문제를 접했을 때는 sum으로 풀면 아주 간단하겠다. 하지만 또 시간초과가 되겠지? 하면서 내가 가장 익숙한 방법인 sum을 이용해 문제를 풀었다. 제출 후 결과를 보니 역시나 시간초과 엔딩..

# 시간 초과

n, m = map(int, input().split())

arr = list(map(int, input().split()))

for _ in range(m):

    i, j = map(int, input().split())

    print(sum(arr[i-1:j]))

---

문제풀이(시간초과2 : input)

그래서 어떤 방식으로 풀어야하지? 고민하다가 누적 합 알고리즘을 알게되었다.

누적 합 알고리즘이란?

리스트의 각 원소에 대해 그 이전 원소들의 합을 미리 구해 구간의 합을 구하는 방법

 

# 누적 합(input때문에 시간초과)

n, m = map(int, input().split())

arr = list(map(int, input().split()))

prefix = [0] * (n+1)

for p in range(1, n+1):

    prefix[p] = arr[p-1] + prefix[p-1]

for _ in range(m):

    i, j = map(int, input().split())

    print(prefix[j] - prefix[i-1])

 

prefix 변수를 이용해 누적 합을 구해 준 다음 i번째 인덱스부터 j까지의 인덱스까지의 합을 구해주었다.

 

그런데 평소처럼 input()으로 푸니 시간초과가 나왔다.

---

문제풀이(정답)

# 정답(input -> sys.stdin.readline)

import sys

input = sys.stdin.readline

n, m = map(int, input().split())

arr = list(map(int, input().split()))

prefix = [0] * (n+1)

for p in range(1, n+1):

    prefix[p] = arr[p-1] + prefix[p-1]

for _ in range(m):

    i, j = map(int, input().split())

    print(prefix[j] - prefix[i-1])

 

input을 sys.stdin.readline으로 받아주니 시간초과 문제가 해결되었다.

 

input vs sys.stdin.readline 속도가 다른 이유?

input() 내장 함수는 sys.stdin.readline()과 비교해서 prompt message를 출력하고, 개행 문자를 삭제한 값을 리턴하기 때문에 느리다.

 

+ 코랩에서는 sys.stdin.readline이 오류가 나기때문에 백준에 제출할 때 바꾸어 제출했다.