003 구간 합 구하기 4

첫번째 코드

 

구간으로 구성된 리스트를 만들어서 해당 구간에 해당 하는 값을 불러와서 더하는 계산을 하라!

 

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

interval = []

for i in range(m):
    start, end = list(map(int, input().split()))
    interval.append((start-1, end-1))
    
for i in range(m):
    answer = sum(number[interval[i][0]:interval[i][1]+1])
    print(answer)

 

시간 초과!

아마 계속 리스트에서 값을 가져와서 반복하는 것이 계산이 많이 필요했던 것 같다!

---

두번째 코드

 

그러면 책에서 배운 아이디어를 사용!

누적합으로 구성된 리스트를 만들어서 그곳에서 계산하도록 생성하자!

 

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

sum_list = [0]
cumul = 0

for i in range(n):
    cumul += number[i]
    sum_list.append(cumul)
    
for i in range(m):
    start, end = map(int, input().split())
    print(sum_list[end] - sum_list[start-1])

 

시간 초과!

ㅇㅅㅇ...왜징...

---

세번째 코드

 

sys.stdin.realine()을 사용하는 것은 input() 함수를 사용하는 것보다 메모리를 적게 사용하며, 대량의 입력을 처리할 때 효율적이다! 내부적으로 더 낮은 수준의 입출력 함수를 사용하기 때문이다!

 

import sys
input = sys.stdin.readline

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

sum_list = [0]
cumul = 0

for i in range(n):
    cumul += number[i]
    sum_list.append(cumul)
    
for i in range(m):
    start, end = map(int, input().split())
    print(sum_list[end] - sum_list[start-1])

 

통과!

앞으로 코딩할 때 input()으로 사용했는데 input = sys.stdin.readline을 해서 사용해야겠다! 똑같은 코드인데... 시간 초과가 뜨다니... 버릇 들여놓으면 좋을 듯 함!

---

링크

https://github.com/ornni/programmers/tree/main/%EB%B0%B1%EC%A4%80/Silver/11659.%E2%80%85%EA%B5%AC%EA%B0%84%E2%80%85%ED%95%A9%E2%80%85%EA%B5%AC%ED%95%98%EA%B8%B0%E2%80%854

programmers/백준/Silver/11659. 구간 합 구하기 4 at main · ornni/programmers