[백준] 18110 solved.ac

J. Hwang·2025년 2월 15일

coding test

목록 보기

101/108

문제

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 × 10^5$ )
이후 두 번째 줄부터 1 + n번째 줄까지 사용자들이 제출한 난이도 의견 n개가 한 줄에 하나씩 주어진다. 모든 난이도 의견은 1 이상 30 이하이다.

출력

solved.ac가 계산한 문제의 난이도를 출력한다.

내 풀이

풀이 1. 리스트를 활용한 풀이

import sys
input = sys.stdin.readline

def roundUp(num):
    if(num - int(num)) >= 0.5:
        return int(num) + 1
    else:
        return int(num)

n = int(input())

if n == 0:
    print(0)
else:
    evals = []
    for _ in range(n):
        evals.append(int(input()))
    evals.sort()
    m = roundUp(n*0.15)
    
    evals = evals[m:n-m]
    
    answer = sum(evals)/len(evals)
    
    print(roundUp(answer))

풀이 2. heap을 활용한 풀이

import sys
import heapq
input = sys.stdin.readline

def roundUp(num):
    if(num - int(num)) >= 0.5:
        return int(num) + 1
    else:
        return int(num)

n = int(input())

if n == 0:
    print(0)
else:
    evals = []
    for _ in range(n):
        heapq.heappush(evals, int(input()))
    m = roundUp(n*0.15)
    for _ in range(m):
        heapq.heappop(evals)
    max1 = heapq.nlargest(m, evals)[:]
    
    answer = (sum(evals)-sum(max1))/(n-2*m)

    print(roundUp(answer))

리스트를 사용하면 sort하는 과정에서 시간 초과가 뜰까봐 heap을 이용해서 풀었는데 왜인지 heap을 이용한 풀이가 324ms로 리스트(144ms)보다 더 오래걸렸다. 원인은 모르겠음....

코멘트

절삭 평균을 이해한다면 쉽게 구현할 수 있는 문제이다. 절삭 평균도 이해하기 어렵지 않은데, 극단적으로 작은 몇 개의 값과 극단적으로 큰 몇 개의 값을 없앤 뒤에 평균을 낸다는 것이다.

이 문제에서 가장 큰 관건은 파이썬의 반올림 시스템을 이해하고 있는지이다. 분명 예제 입출력과 동일하게 나오고 구현한 로직 상으로도 문제가 없는데도 계속 오답이 나와서 검색을 해보니 모든 풀이들에서 반올림 문제를 얘기하고 있었다.

보통 파이썬에서는 round 함수를 이용해서 반올림을 하는데, 이는 우리가 수학 시간에 배운 반올림과는 방식이 다르다. 우리가 수학 시간에 배운 바에 따르면 (이를 사사오입 반올림 (Round Half Up) 이라고 한다)

$0 < x < 0.5 → 0$
$0.5 \leq x < 1 → 1$

과 같이 반올림되는데, 파이썬에서 round(4.5)를 해보면 5가 아니라 4가 나오는 것을 확인할 수 있다. 이는 파이썬의 은행가 반올림 (Bankers' Rounding) 또는 짝수 반올림 (Round Half to Even) 방식 때문으로, 반올림할 숫자가 .5일때는 가장 가까운 짝수로 반올림되기 때문이다. 파이썬이 이런 방식으로 반올림하는 이유는 사사오입 반올림을 사용하는 경우 .5에서 항상 큰 수 방향으로 반올림되면서 통계적으로 값이 커지는 bias가 생기는데, 은행가 반올림을 이용해서 값을 균형있게 분배하여 bias를 줄이기 위한 것이라고 한다.

따라서 반올림을 하는 함수를 따로 구현하여 문제를 풀면 정답을 받게 된다.

다만 round 함수를 보완하고자 math.ceil을 사용했을 때도 계속 오답 처리가 되었는데, 그 원인은 잘 모르겠다.