사용자 도구

사이트 도구


ps:problems:boj:18110

solved.ac

ps
링크acmicpc.net/…
출처BOJ
문제 번호18110
문제명solved.ac
레벨실버 4
분류

기초

시간복잡도O(nlogn)
인풋사이즈n <= 3*10^5
사용한 언어Python 3.11
제출기록38352KB / 148ms
최고기록144ms
해결날짜2023/06/05

풀이

  • 그냥 시키는대로 처리해주면 되는 문제.
  • 투표값들중 상위 15%, 하위 15%를 제거하는 것은, 값이 1~30 범위 안에 들어오기때문에, 값별로 카운트를 세어서 처리하면 효율적으로 O(n)에 처리가 가능하다. 하지만, 그냥 모든 투표를 리스트에 저장한뒤에 정렬해서 처리하는것이 코딩면에서는 훨씬 간단하기에 이렇게 처리했다. 이 경우에는 정렬이 필요하므로 시간복잡도는 O(nlogn)이 된다.
  • 제외되는 수와, 최종 값을 자연수로 표현하기 위해서 반올림을 하라고 지문에는 적혀있으나, 어떤 방식의 반올림을 하라고 설명이 누락되어있다. (반올림에는 다양한 방법이 있다)
  • 실제로 문제에서 원하는 것은 cpp식 반올림이고, 그래서 python의 내장 round 함수를 사용하면 오답이 된다. 직접 반올림 함수를 구현해서 처리해야 했다.

코드

"""Solution code for "BOJ 18110. solved.ac".

- Problem link: https://www.acmicpc.net/problem/18110
- Solution link: http://www.teferi.net/ps/problems/boj/18110
"""

import sys


def round_half_up(x):
    if x > 0:
        return int(x) + 1 if x - int(x) >= 0.5 else int(x)
    else:
        return int(x) - 1 if int(x) - x >= 0.5 else int(x)


def main():
    n = int(sys.stdin.readline())
    ratings = [int(sys.stdin.readline()) for _ in range(n)]

    if n == 0:
        print('0')
        return

    exclusion_count = round_half_up(n * 0.15)
    effective_ratings = (
        ratings
        if exclusion_count == 0
        else sorted(ratings)[exclusion_count:-exclusion_count]
    )
    answer = round_half_up(sum(effective_ratings) / len(effective_ratings))

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
B U A W A
 
ps/problems/boj/18110.txt · 마지막으로 수정됨: 2023/06/05 06:10 저자 teferi