[Python] 백준 11659 문제 풀이, 구간 합, 입출력 속도 개선

시작에 앞서 온라인 디버거 하나 추천

1학년 때부터 이 온라인 디버거를 사용해서 코딩을 하는데 아주 편하다...

모든 언어를 하나의 환경에서 짜볼 수 있다는 게 좋은 것 같음 ㅎㅎ 굿

https://www.onlinegdb.com/

GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C++

 

 

 

먼저 문제를 풀기 전에 구간 합에 대하여 알아보자

내가 이해한 구간 합의 정의는 리스트의 합을 합 배열에 넣어서 시간 복잡도를 감소시켜 빠른 속도로 문제를 푸는 것이다.

 

합 배열 S의 공식은 다음과 같다. 

S[i] = S[i-1] + A[i]

(당연함...)

 

그렇다면 구간 합을 구하는 공식을 알아보자

S[j] - S[i-1]

위의 공식은 i에서 j까지의 구간 합이다 (이것도 당연함...)

 

 

ex) 

나는 현재 A[3]~A[5] 구간 합을 합 배열로 구하려 한다.

 

 

공식을 통해서 생각해보면 S[5] - S[2]로 풀면 될 것 같다... 과연?

S[5] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]

S[2] = A[0] + A[1]

S[5] - S[2] = A[2] + A[3] + A[4] + A[5]

 

굿

 

 

 

 

구간 합을 합 배열로 구하는 과정에 대하여 배웠으니 문제를 풀어보자.

 

Do it! 알고리즘 코딩 테스트: 파이썬 편:코딩 테스트를 처음 준비하는 취준생의 필독서!

 

DO IT 알고리즘 코딩 테스트 문제 3번, p.43부터 시작한다. 

 

 

 

# 문제 003 구간 합 구하기 1 (백준 11659)

 

수 N개가 주어졌을 때 i번째 수까지의 합을 구하는 프로그램을 작성하시오.

백준 온라인 저지 11659 문제랑 동일하다.

 

 

문제가 이해가 안 되면 아래 링크 참고!

11659번: 구간 합 구하기 4

 

 

먼저 수의 개수 N과 합을 구해야 되는 횟수 M을 입력받는다.

 

N, M = map(int, input().split())

 

 

 

그리고 N개의 숫자를 입력받는다.

N개의 숫자를 입력받은 후 list에 넣어주기 위해 다음과 같이 코드를 짰다.

 

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

 

이후 i와 j를 입력받아서 i번째 수에서 j번째 수까지의 합을 구하면 된다.

그러나 구간마다 합을 계산하면 문제에 주어진 제한 시간인 0.5초 만에 모든 구간 합 계산을 끝낼 수 없다.

따라서 구간 합을 사용해야 된다.

 

 

 

합 배열을 만들어주기 위한 코드

 

sumList = [0]

sum = 0
for i in nList:
    sum += i
    sumList.append(sum)

 

합 배열에는 nlist에 있는 값 순서대로 하나씩 들어가서 합을 저장해줘야 되므로 append() 함수 사용

이때 sumList에 0은 기본값을 넣어줌 sumList[0] = 0이 되어야 공식 사용 가능 

 

 

 

 

그렇다면 출력값을 구하기 위한 공식을 짜보자.

먼저 i, j를 입력받아야 된다.

이때 M값만큼 반복되어야 되므로

 

for num in range(M):
    i, j = map(int, input().split())

 

for문을 사용하여 M번만큼 반복시킨다.

 

이때 출력값을 for문에서 저장한 뒤 출력하기 위해 answerList라는 변수를 이용하여 구간 합을 list화 해줬다. (출력을 위한 list)

마찬가지로 append() 함수 사용

 

for num in range(M):
    i, j = map(int, input().split())
    answerList.append(sumList[j]-sumList[i-1])

 

** 구간 합 공식 사용**

i부터 j까지의 합이므로 sumList[j] - sumList[i-1]

 

 

이후 answerList를 출력

 

for num in range(M):
    print(answerList[num])

 

 

 

 

전체코드

 

N, M = map(int, input().split())
nList = list(map(int, input().split()))
sumList = [0]
answerList = []

sum = 0
for i in nList:
    sum += i
    sumList.append(sum)

for num in range(M):
    i, j = map(int, input().split())
    answerList.append(sumList[j]-sumList[i-1])

for num in range(M):
    print(answerList[num])

 

 

근데 제출하면 한 번은 정답이라고 뜨고 한 번은 시간 초과라 뜬다...

(일단 정답이라 뜨긴 했음)

근데 더 간단한 방법이 있을 것 같다.

 

 

 

 

+ 다른 풀이

시간 초과 개선 방법을 찾았다!!

 

입력받을 땐 input()보단 readline()을 쓰는 것이 훨씬 빠르다고 한다.

 

 

readline() 함수 사용법

 

import sys

n = int(sys.stdin.readline())

 

이렇게 사용하면 된다. 그럼 다시 코드를 짜보자.

코드를 짤 땐 input에 readline 함수를 대입해줘서 풀었다.

 

import sys 

input = sys.stdin.readline
N, M = map(int, input().split())
nList = list(map(int, input().split()))

sumList = [0]

sum = 0
for i in nList:
    sum += i
    sumList.append(sum)

for num in range(M):
    i, j = map(int, input().split())
    print(sumList[j]-sumList[i-1])

 

 

아래 정답 결과는 input()을 사용했을 때고

위 정답 결과는 sys.stdin.readline을 사용했을 때의 결과다. 

시간이 훨씬 덜 걸린 것을 확인할 수 있었다. 굿 애용하자