Baekjoon 1655 가운데를 말해요 JAVA

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

1655번: 가운데를 말해요

 

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%201655

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 숫자가 주어질 때마다 전체 정렬된 숫자 중에 중간인 숫자를 출력하는 문제다

숫자가 짝수 개이면 중간 두 개의 숫자 중 작은 숫자를 출력한다.

​

처음에 문제를 보고 우선순위 큐 하나를 만들고 값을 입력받으면서 중간값을 구하면 되겠다고 생각했는데.

​

이게 중간값을 체크하기 위해서 빼주고 다시 넣어주고 하는 부분들이 잘못 생각했다고 느꼈고,

우선순위 큐를 두 개 두어서 하나는 오름차순, 하나는 내림차순으로 정렬하고

내림차순 큐에서 하나씩 peek 해서 보여주면 되겠다고 생각했다.

​

내림차순은 람다식을 이용했다.

​

먼저 큐 두 개의 사이즈가 같으면 내림차순 큐에 일단 넣어준다.

만약 큐 사이즈가 다르면 오름차순 큐에 넣어주고 이후 내림차순 큐와 오름차순 큐의 젤 앞부분을 비교하는데

내림차순 큐의 제일 앞이 오름차순 큐의 제일 앞보다 크다면 둘을 바꿔주고

​

이후 내림차순 큐에 젤 앞부분을 StringBuilder에 저장하고

최종 출력해 주었다.

아래 그림은 1 2 3 4 5가 입력으로 들올 때 예시를 이해하기 쉽도록 그림으로 나타내었다.