시간복잡도는 완벽히 알고있는 듯 한. (#11659번 구간 합 구하기 4)

#11659번 구간 합 구하기 4 https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

어렵진 않았지만 시간초과가 나서 너무 짜증났던 문제

 

틀린코드 1

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

for _ in range(m):
    i, j = map(int, input().split())
    print(sum(nums[i-1:j]))

매 케이스 마다 합을 구했다. 이건 시간초과가 날거라고 예상하고 작성했기에 얼른 변경했다.

 

틀린코드 2

n, m = map(int, input().split())
nums = list(map(int, input().split()))
for i in range(n):
    nums[i] = sum(nums[i:])
# print(nums)
for _ in range(m):
    i, j = map(int, input().split())
    if j >= n:
        print(nums[i-1])
    else:
        print(nums[i-1] - nums[j])

새로 입력되는 수 마다 합을 구한다. 하지만 시간초과.

sum함수를 쓰면 안되겠다는 생각이 들었다.

 

틀린코드 3

n, m = map(int, input().split())
nums = list(map(int, input().split()))
for i in range(1, n):
    nums[i] += nums[i-1]
# print(nums)
for _ in range(m):
    i, j = map(int, input().split())
    if i-2 >= 0:
        print(nums[j-1] - nums[i-2])
    else:
        print(nums[j-1])

리스트 상에서 누적 합을 구한다. 약간 DP같은 느낌이라고 생각하면 될 것 같다. 

이것도 시간초과가 나서 너무 짜증이 났다 ㅋㅋㅋ

 

틀린코드 4

n, m = map(int, input().split())
nums = input().split()
for i in range(n):
    if i == 0:
        nums[i] = int(nums[i])
    else:
        nums[i] = nums[i-1] + int(nums[i])
# print(nums)
for _ in range(m):
    i, j = map(int, input().split())
    if i-2 >= 0:
        print(nums[j-1] - nums[i-2])
    else:
        print(nums[j-1])

두 번째 줄에서 생긴 문제라고 판단하고 다른 방법을 선택했다. 그런데도 시간초과가 나서 결국 질문을 찾아봤다.

 

그냥 sys.stdin.readline 안써서 발생한 문제였다.

 

틀린코드 3과 틀린코드 4에 input = sys.stdin.readline을 적용하면 시간초과가 나지 않는다.

 

문제의 핵심은 sum함수를 쓰지 않고 합을 적절히 구해내는 방법을 고안하는거라고 생각한다.

 

정답 코드 중 가장 빠른 코드

from sys import stdin
input = stdin.readline
n, m = map(int, input().split())
nums = input().split()
for i in range(n):
    if i == 0:
        nums[i] = int(nums[i])
    else:
        nums[i] = nums[i-1] + int(nums[i])
# print(nums)
for _ in range(m):
    i, j = map(int, input().split())
    if i-2 >= 0:
        print(nums[j-1] - nums[i-2])
    else:
        print(nums[j-1])

확실히 시간복잡도를 줄이기 위해서 노력했던 코드인 틀린코드 4가 가장 빨랐다.