[python] 소프티어 - 성적 평균

소프티어 lv3 문제
https://softeer.ai/practice/info.do?idx=1&eid=389&sw_prbl_sbms_sn=204906

언어별 시간/메모리
Python : 2초, 256MB

문제
N명의 학생들의 성적이 학번순서대로 주어졌다.

학번 구간 [A, B]가 주어졌을 때 이 학생들 성적의 평균을 구하는 프로그램을 작성하라.

제약조건
1 ≤ N ≤ 106 인 정수

1 ≤ K ≤ 104 인 정수

1 ≤ Si ≤ 100 인 정수

1 ≤ Ai ≤ Bi ≤ N

입력형식
첫 번째 줄에 학생 수 N과 구간 수 K가 주어진다.

두 번째 줄에는 학생의 성적 Si (1 ≤ i ≤ N)가 주어진다. i + 2 (1 ≤ i ≤ K)번째 줄에는 i번째 구간 Ai, Bi가 주어진다.

출력형식
i번째 줄에 i번째 구간의 성적평균(소수셋째자리에서 반올림)을 출력한다.

차이가 0.01이하이면 정답으로 채점됨.

입력예제1
5 3
10 50 20 70 100
1 3
3 4
1 5
출력예제1
26.67
45.00
50.00

---

로직은 쉽지만 소수점자리를 0으로 채우는 방법을 지난 회의실 예약에서 배웠던 내용을 활용해야했다.

내 코드

# N명의 학생들의 성적이 학번순서대로 주어짐
# 학번 구간 [A,B]가 주어졌을 때 이 학생들 성적의 평균을 구하는 프로그램

N, K = map(int, input().split()) # 학생수, 구간수

scores = list(map(int, input().split()))
scores.insert(0,-1)

for i in range(K):
    section = list(map(int,input().split()))
    scoresSum = sum(scores[section[0]:section[1]+1])
    print(f'{round(scoresSum/(section[1]-section[0]+1),2):.2f}')

오늘의 학습

• 반올림 : round(값, 자리수)
• 소수점 0으로 채우기 : print(f'{값:.2f}')

지난 번엔 2자리 정수를 1자리 일 때는 0으로 채우는 것이라서

• 값:02d
  - d(정수)를 0 으로 2자리수만큼 채운다

로 했지만 이번엔

• 값:.02f
  - f(실수)를 . (소수점 이하를) 0으로 2자리수만큼 채운다

로 사용했다.

해설강의

해설을 보니 시간복잡도가 O(KN) 이 나오면 연산이 $10^{10}$이 나와서 시간초과라고 했다.
나는 for문안에 sum() 을 넣었으니 시간초과가 나와야할 것 같은데 왜 안나왔지?

어쨌든 난 너무 쉽게 풀었다. 잘못된 풀이다. O(KN), O(백억)이므로 시간초과가 나와야한다.

---

풀이

각 점수마다 그 점수까지의 구간합을 구해놓는다.
그 방식은 이전까지의 구간합 + 현재 점수 방식으로 한다.

# N명의 학생들의 성적이 학번순서대로 주어짐
# 학번 구간 [A,B]가 주어졌을 때 이 학생들 성적의 평균을 구하는 프로그램

N, K = map(int, input().split()) # 학생수, 구간수

scores = list(map(int, input().split()))
scores.insert(0,0) # 인덱스 맞추기위해
scoresSum = [0] * (N+1) # 구간합 초기화
scoresSum[1] = scores[1] # 구간합을 구하기위해 1번 학생의 점수 입력

for i in range(2,N+1):	# 구간합 구하기
    scoresSum[i] = scoresSum[i-1]+scores[i]
    
for i in range(K):  # 구간별 평균 출력
    start, end = map(int,input().split())
    result = round((scoresSum[end]-scoresSum[start-1])/(end-start+1),2)
    print(f'{result:.02f}')

사실은 DP문제 였다.

처음 코드의 결과

수정한 코드의 결과

실행시간의 차이가 있다.