문제
solved.ac는 Sogang ICPC Team 학회원들의 알고리즘 공부에 도움을 주고자 만든 서비스이다. 지금은 서강대뿐만 아니라 수많은 사람들이 solved.ac의 도움을 받아 알고리즘 공부를 하고 있다.
ICPC Team은 백준 온라인 저지에서 문제풀이를 연습하는데, 백준 온라인 저지의 문제들에는 난이도 표기가 없어서, 지금까지는 다양한 문제를 풀어 보고 싶더라도 난이도를 가늠하기 어려워 무슨 문제를 풀어야 할지 판단하기 곤란했기 때문에 solved.ac가 만들어졌다. solved.ac가 생긴 이후 전국에서 200명 이상의 기여자 분들께서 소중한 난이도 의견을 공유해 주셨고, 지금은 약 7,000문제에 난이도 표기가 붙게 되었다.
어떤 문제의 난이도는 그 문제를 푼 사람들이 제출한 난이도 의견을 바탕으로 결정한다. 난이도 의견은 그 사용자가 생각한 난이도를 의미하는 정수 하나로 주어진다. solved.ac가 사용자들의 의견을 바탕으로 난이도를 결정하는 방식은 다음과 같다.
아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다.
의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30% 절사평균으로 결정한다.
절사평균이란 극단적인 값들이 평균을 왜곡하는 것을 막기 위해 가장 큰 값들과 가장 작은 값들을 제외하고 평균을 내는 것을 말한다. 30% 절사평균의 경우 위에서 15%, 아래에서 15%를 각각 제외하고 평균을 계산한다. 따라서 20명이 투표했다면, 가장 높은 난이도에 투표한 3명과 가장 낮은 난이도에 투표한 3명의 투표는 평균 계산에 반영하지 않는다는 것이다.
제외되는 사람의 수는 위, 아래에서 각각 반올림한다. 25명이 투표한 경우 위, 아래에서 각각 3.75명을 제외해야 하는데, 이 경우 반올림해 4명씩을 제외한다.
마지막으로, 계산된 평균도 정수로 반올림된다. 절사평균이 16.7이었다면 최종 난이도는 17이 된다.
사용자들이 어떤 문제에 제출한 난이도 의견 목록이 주어질 때, solved.ac가 결정한 문제의 난이도를 계산하는 프로그램을 작성하시오.
입력
첫 번째 줄에 난이도 의견의 개수 n이 주어진다. (0 ≤ n ≤ 3 × 105)
이후 두 번째 줄부터 1 + n번째 줄까지 사용자들이 제출한 난이도 의견 n개가 한 줄에 하나씩 주어진다. 모든 난이도 의견은 1 이상 30 이하이다.
출력
solved.ac가 계산한 문제의 난이도를 출력한다.
풀이 과정
풀면서 3번 정도 오답을 제출했었는데, 원인은 크게 2가지로 볼 수 있다.
1. python 의 round 함수는 오사오입이다.
문제에 주어진 반올림을 수행하려고 했을 때 가장 먼저 떠오른 것은 round 함수 였다.
round 함수의 원형은 round(number [, ndigits]) 형태로,
반환형은 다음과 같다.
인자로 온 number 가 숫자 타입인 경우 정수 or 실수 반환
첫 인자 number 에는 반올림 하고 싶은 숫자를 넣어주고, 두 번째 인자 ndigits는 소수점 몇 번째까지 반올림 하고 싶은지를 적어주면 된다.
원래 어느 정도 알던 사실이였는데, 한 가지 간과했던 사실이 바로 round 함수는 오사오입 을 적용한다는 사실이였다.
예시를 들어 보자.
round(0.5) : 0 ???? (0.5의 반올림은 1인데 왜 0이 프린트될까)round 의 경우 오사오입을 적용하여 5 미만의 숫자는 버리고, 5 초과의 숫자는 올림을 진행한다. 5일때 처리해 주는 방식이 우리가 일반적으로 아는 사사오입 방식과 다르다.
만약 5의 앞자리가 짝수인 경우 버림을 진행하고, 5의 앞자리가 홀수인 경우 올림을 진행한다.
따라서 0.5의 경우 5의 앞자리가 0(짝수)이기 때문에 버림을 진행하여 0이 되는 것.. 이 부분을 놓치고 있었다.
따라서 round 를 계속 쓰지 않고, math 라이브러리를 import 해서 기존 값에 0.5를 더한 후 floor(내림)을 하는 식으로 사사오입을 구현했다.
math.floor(answer/n + 0.5)예를 들어 answer 가 3.5이고 n 이 1이라면
3.5/1 + 0.5 = 4 가 되는 것이고, 이전 방식대로 round를 사용했더라면 답은 3이였겠지만 현재는 4가 되는 것을 볼 수 있다.
2. 파이썬의 빠른 입출력
제출 시 시간 초과가 나서, 빠른 입출력에 대해서 탐구해보기로 했다.
빠른 데이터 입출력을 수행하기 위해서는 sys 라이브러리 를 활용하면 된다.
먼저 빠른 입력에 대해 알아보자
import sys
input = sys.stdin.readline
data = input().rstrip()보통 이런 형식으로 사용한다. 이 방식대로 변수에 sys.stdin.readline 을 사용하면 보다 편리하게 사용할 수 있다. 또한 sys.stdin.readline 은 줄바꿈 문자가 포함되어 입력을 받는데, rstrip() 함수를 활용해 줄바꿈 문자를 제거해야 한다.
이를 활용하여 시간 초과 문제를 해결하였다
그렇다면 빠른 출력 에 대해 알아보자
import sys
print = sys.stdout.write
print('hello')
print('mr') -> 출력형식 -> hellomr빠른 입력과 방식은 동일하다. 다만 이 방식을 사용해 출력하면 줄바꿈이 자동으로 수행되지 않는다는 점을 기억해 두자..!
최종 코드는 다음과 같다.
import math
import sys
input = sys.stdin.readline
n = int(input().rstrip())
list1 = []
for i in range (0,n):
a = int(input().rstrip())
list1.append(a)
list1.sort()
if n==0: #아직 아무 의견이 없다면 문제의 난이도는 0으로 결정한다.
print(0)
else: #의견이 하나 이상 있다면, 문제의 난이도는 모든 사람의 난이도 의견의 30% 절사평균으로 결정한다.
jeolsanum = math.floor(n * 0.15 + 0.5) #위에서 15퍼, 아래서 15퍼 제외(반올림)
if jeolsanum == 0: #이 경우엔 제외할 것이 없음..
answer = 0
for i in list1:
answer += i
print(math.floor(answer/n + 0.5))
else:
list1 = list1[jeolsanum:(n-jeolsanum)]
answer2 = 0
for i in list1:
answer2 += i
print(math.floor(answer2/len(list1) + 0.5))