백준 / 18110번 / solved.ac / Python / 수학,구현,정렬,deque

📚문제

출처 : 백준 18110번 (https://www.acmicpc.net/problem/18110)

📝풀이

# 18110 solved.ac (Silver IV)
import sys
from collections import deque
n = int(input())

def rround(n): return int(n)+1 if n-int(n)>=0.5 else int(n) # 사사오입 공식
p = rround(n*0.15) # 절사 값
level_list = []

if n == 0:
    print(0)
else:
    for i in range(n):
        level_list.append(int(sys.stdin.readline().rstrip()))
    level_list = deque(sorted(level_list))
    
    if p != 0:
        for _ in range(p):
            level_list.popleft()
            level_list.pop()
    print(rround(sum(level_list)/len(level_list)))

 

시간 초과 문제 뿐만 아니라 

round 함정까지 내포되어있는 문제

절사 값 p를 구할 때도 나는 그냥 

round로 구해주고 n=1,2,3인 경우는 p가 0이 되니까

그 경우도 나눠서 풀어 줬는데 그러면 오답이 된다

 

구글링해보니

파이썬의 round 함수는 기본적으로 5사5입을 따른다

*5사5입 : 반올림 자리가 5인경우 앞자리가 홀수면 올림, 짝수면 버림을 택한다 (round_half_even)

 

그렇기 때문에 우리가 기존에 알던 반올림 방식으로 문제를 풀고 싶으면

4사5입 함수를 도입해서 풀어주어야 한다

참고링크 출처 : https://www.acmicpc.net/board/view/53941

def rround(n): return int(n)+1 if n-int(n)>=0.5 else int(n) # 사사오입 공식

 

1) 절사값을 구할 때(n*0.15)

2) 마지막 최종 값을 구할 때

모두 이 4사5입함수(rround)를 사용하지 않으면 틀린 것으로 간주된다

 

 

+ 그리고 deque(덱) 개념을 이번에 배우게 됐다

기존의 queue(큐)는 선입선출(FIFO) 방식으로 동작하는데 이런 큐가 양방향으로 있는것(double-ended queue)

앞 뒤 양쪽 방향에서 원소 추가 및 제거 가능

데크는 양쪽 원소의 pop 과 append가 빠름

참고링크 출처 : https://chaewonkong.github.io/posts/python-deque.html

 

*컨테이너(container)의 양끝 엘리먼트(element)에 접근하여 삽입 또는 제거를 할 경우

=> 일반적인 리스트(list)가 이러한 연산에 O(n)이 소요 / 데크(deque)는 O(1)로 접근 가능하다.

 

*컨테이너 : 여러 요소를 담을 수 있는 데이터 구조 . 파이썬에서는 튜플,집합,리스트,딕셔너리 등 (출처 : ChatGPT)

 

📌 deque와 queue 모두 데이터 추가/삭제는 O(1), 데이터 접근은 O(n)의 시간 복잡도를 가진다