백준 11659 - 구간 합 구하기 4

좋은 기회로 코테 스터디에 들어가게 됐다!

파이팅...

---

 

우선 개최자(?)님이 문제 풀이 팁으로 python 기준, input() 말고 sys.stdin.readline()을 사용하는 것을 추천해 쥬심.

해당 사항에 궁금증이 생겨 이것부터 내용 정리를 시작하갯습니다.

 

input()은 시간 초과 에러가 종종 발생하는 데에 비해 sys.stdin.readline()은 처리 속도가 빨라 더 유리하다고 한다.

이유는 아래와 같다.

1. input()은 매개변수로 prompt message를 받는다. (따라서 입력을 받기 전에 prompt message를 출력해야 한다.)
2. input()은 입력받은 값의 개행 문자를 삭제시키고 반환한다.

input()은 위 단계를 거치기 때문에 속도가 더 느린 것이다!

 

여기에서 prompt message는 a = input("안녕하세요")에서 안녕하세요와 같은 부분을 의미한다.

메시지를 입력받지 않더라도 속도 지연에 작용될 수 있다고 한다. (왜지)

 

이에 반해 sys.stdin.readline()은 애초부터 문자열을 입력으로 받는다.

때문에 이를 정수, 실수, 리스트 등으로 사용하고 싶다면 함수 처리를 거쳐야 한다.

import sys

b = sys.stdin.readline() # input: "Hello World\n"
print(b)

결과: "Hello World\n"

 

변환은 간단하다. input과 비슷하게 앞을 int, float 등으로 감싸 주면 된다.

import sys

c = int(sys,stdin.readline()) # 2026
print(c)

결과: 5

 

개행 문자 없이 문자열을 입력받고 싶다면 strip()을 추가하면 된다.

import sys

d1 = sys.stdin.readline().strip()
d2 = sys.stdin.readline().strip('\n')
d3 = sys.stdin.readline().rstrip('\n')

print(d1, d2, d3)

입력:

Hello World

Hello World

Hello World

 

출력:

Hello World Hello World Hello World

 

strip()은 문자열 양 옆의 \n(줄 바꿈), \t(공백)를 제거한다.

rstrip()은 문자열의 오른쪽 \n, \t를 제거한다.

-> 매개변수로 \n 혹은 \t를 입력하면 해당 문자를 문자열에서 제거할 수 있다.

 

---

 

이제 문제를 풀어보자.

개수: N (배열)

합을 구해야 하는 횟수: M (구간 합)

*구간 합: 수들의 나열에서 특정 구간의 합. 보통 1차원 배열에서 i-k 인덱스 사이의 값들의 합을 구하는 데 사용함.

 

1,000보다 작거나 같은 N개의 수가 주어지고

M개의 줄에는 합을 구해야 하는 구간 i, j가 주어짐

1. 입력으로 5 3이 들어옴 -> N, M을 한 줄에 입력받기 (map, int)

2. 5개의 배열: 5 4 3 2 1 -> 즉. N의 배열을 입력받아야 함 (list, map -> 입력받은 정수를 분리한 후 리스트 형태로 저장)

3. 세 번의 구간합 - 1: 1 3

4. 세 번의 구간합 - 2: 2 4

5. 세 번의 구간합 - 3: 5 5

 

*

map을 통해 5, 3을 받으면 내부에서는 N = 5, N = 3 이렇게 매치됨 (분리되어 저장됨)

두 번째 줄에서는 list 형태로 만들어 줘야 누적 합에서 사용 가능

 

코테도 오랜만이고 해당 개념을 잘 몰라서 꽤나 많은 시행착오를 겪었는데 일단 간략히 정리하면 아래와 같음

1. 이중 for문 사용 -> error

2. map 까먹어서 N, M 따로 입력받기... ^^

3. 구간 합 식 설계

이 정두.......

 

import sys

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

sum1 = [0] 
sum2 = 0 

for i in a:
    sum2 = sum2 + i
    sum1.append(sum2)
    
for k in range(M):
    i, j = map(int, sys.stdin.readline().split())
    print(sum1[j]-sum1[i-1])

 

sys.stdin.readline()을 사용하기 위해 import sys

 

N, M을 한번에 입력받기 위해 map, split

N의 리스트를 입력받기 위해 a를 list, map으로 받음

 

sum1은 리스트 형태, sum2는 정수 형태로 정의

 

누적 합은 a번(= N번) 동안, a0부터 an-1까지 순회하며 더하여 최종 값을 저장,

동시에 sum1에는 리스트 형태로 각 구간의 합을 저장함

 

그리고 구간 합을 구하기 위해 for k in range(M):

함수 안에 i, j 값을 map(int, sys.stdin.readline().split())을 통해 분리하여 받고

print(sum1[j]-sum1[i-1]) -> 3, 4, 5번째 줄의 결과

 

구간 합은 공식 서치하니까 납득됐다

코테 풀 때 가장 현타 오는 순간 = 수학 식 때문에 틀렸을 때

 

 

 

-------

코테 수업 피드백

 

append를 사용하면 느려짐 -> 메모리 할당을 중간에 해야 하기 때문

때문에 리스트를 생성하여 진행하는 게 더 나음

 

sum2가 없어도 됨 -> 메모리 효율성을 위함

파이썬 표준 for _ in range() -> i가 필요 없을 때 사용

 

input보다 sys.stdin.readline이 훨씬 빠름!

 

 

---

출처

https://yeomss.tistory.com/120

https://hroad.tistory.com/52