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

난이도: 골드 2

문제 링크: www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

제한 시간이 매우 짧은 (0.1초) 문제입니다.

반면 메모리는 상대적으로 넉넉한 편인 문제 같네요.

 

저는 다음과 같이 접근했습니다.

1. 두 개의 Priority Queue minPQ, maxPQ를 둡니다. minPQ는 제일 작은 수가 top에, maxPQ는 제일 큰 수가 top에 위치합니다.
2. 수를 입력 받아서 다음을 기준으로 push합니다.
   1. maxPQ의 element 수는 minPQ와 같거나 1 큽니다.
   2. minPQ의 top은 maxPQ의 top과 값이 같거나 더 큽니다. 이것이 성립하지 않을 경우 두 top값을 swap 합니다.
3. push 후 maxPQ의 top값이 중간값이 됩니다. 이를 출력합니다.

간단하게 설명하면 다음과 같습니다.

우리의 목적은 중간값을 찾는 것입니다. 이를 위해 하나의 배열을 두고 매번 중간값을 찾는 것은 시간이 너무 많이 걸리고 비효율적입니다.

따라서 두 개의 배열을 둡니다. 작은 숫자일수록 maxPQ에 들어가고, 큰 숫자일수록 minPQ에 들어갑니다.

maxPQ의 element 수는 minPQ와 같거나 1 큽니다. 같은 경우는 전체 element 수가 짝수일 때이고, 1 클 때는 element 수가 홀수일 때입니다. 홀수일 때는 중간값이 명확하고, 짝수일 때는 더 작은 값 (예: 6개일 경우 3번째 값이 중간값)이 중간값이 됩니다.

따라서 작은 수들의 배열 중 가장 큰 값이 항상 중간값이 됩니다. 이것을 매번 출력해 줍니다.