[백준] 1655번: 가운데를 말해요 - python

문제풀이

https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

 

 

---

풀이 및 코드

 

해당 문제는 단순하게 가운데 숫자만 찾으면 된다고 생각할 수 있지만 입력의 크기가 100,000으로 매우 크기 때문에 sort해서 가운데 숫자를 출력하면 시간초과가 발생하게 된다. 

 

""" 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. """

 

 

 

필자는 중앙값보다 작은 배열 left와 큰 배열인 right로 나누어 생각했다. 새로 들어온 문자가 이전 차례의 중앙값인 m보다 작다면 left에 추가되고 크다면 right에 추가된다. 그리고 나서 max(left), min(right) 와 m을 적절히 분배해 left와 right의 크기를 같도록 혹은 right가 1 크도록 만들어 준다면 새로운 중앙값 m을 도출할 수 있다. 요약한다면 다음과 같다.

 

 

 

# 두가지 조건이 만족하면 m은 중앙값이다.

•  left  < m < right
• len(left) == len(right) or len(left) == len(right)+1

 

 

 

앞서 말한 것처럼 이를 list로 구현한다면 아마 시간초과가 발생할 것이다. 새로운 값이 들어올때마다 새롭게 sort를 한다면 굉장히 오랜 시간이 걸린다(sort의 시간복잡도는 nlog(n)이다). 따라서 list 보다는 heap을 쓰는 것이 좋다. 일반적인 heap인 최소힙은 root값인 최솟값을 찾기에 가장 효율적이다. 따라서 left는 최대힙으로 right는 최소힙으로 구성해 필요할 때에 left에서 큰 값을 찾고 right에서 작은 값을 찾도록 구현했다.

 

 

 

이렇게 만들어도 통과는 되지만 필자는 시간을 더 줄이고 싶어서 새로운 문자가 들어왔을 때 left나 right에 바로 추가하지 않고 left와 right의 길이를 먼저 확인해주었다.

 

예를 들어 새로 들어온 숫자가 m보다 작은 상황을 가정해보자. m보다 작기때문에 새로운 숫자는 left에 추가 되어야 하지만, 필자는 left와 right를 먼저 비교해서 len(left) >= len(right)라면 기존 m을 right에 넣어주고 새로운 숫자를 포함한 left에서 새로운 m을 추출했다. 만약 left < right 였다면 left에 새로운 숫자를 추가하고 중앙값은 변하지 않았을 것이다.