[백준]가운데를 말해요/1655 풀이 JAVA

문제

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

 

풀이(JAVA)

최소힙, 최대힙을 이용하는 문제였다!

나는 이 개념을 아직 몰라서 유튜브에서 영상 보고 이해했음

(https://youtu.be/jfwjyJvbbBI)

최대힙은 루트에 최댓값이 있는 이진트리이고,

최소힙은 루트에 최소값이 있는 이진트리라고만 기억해두자.

 

문제 풀이는... 짧게 요약하면 아래 3단계로 나뉨

1. 먼저 for 문을 돌려 i가 짝수면 maxHeap에 저장하고, 홀수면 minHeap에 저장하도록 했다.
2. maxHeap의 루트 > minHeap의 루트면 swap한다.
3. 그러면 중간값은 maxHeap의 루트가 된다!!

 

Q, 왜 짝수 홀수를 나눠 저장하지?

A, 각 힙에 숫자가 반반씩 들어가야해서(그래야 중간값을 구할 수 있음)

 

Q,짝수 홀수를 정하는 기준은 뭐임?

A, 우리는 maxHeap의 루트에 중간값이 있게 할 것이고, 수빈이가 처음으로 숫자 하나를 외칠 때, 즉 i=0일 때(홀수취급)의 중간값을 잘 출력하기 위해선 i가 홀수일 때 maxHeap에 저장되게 해야함

 

Q, 왜 maxHeap의 루트를 출력함? minHeap의 루트 출력하면 안됨?!

A,  "수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다."라는 조건 때문.

문제 예시인  1, 5, 2, 10, -99, 7, 5를 힙에 각각 넣어보면

maxHeap : -99, 1, 2, 5 (루트는 5)

minHeap : 5, 7, 10 (루트는 5)

이렇게 들어감!

그러니까 maxHeap의 루트에는 작은 숫자 중에 최댓값을 가지고 있는 거고,

minHeap의 루트는 큰 수 중에 최솟값을 가지고 있는 것이 됨!!

그래서 더 작은 수인 maxHeap의 루트를 출력해야 함.

 

Q, 그걸 어케 하는데...? 어케 작은 숫자는 maxHeap에, 큰 숫자는 minHeap에 들어가게 하는데...?

A, 짝홀수대로 숫자 하나씩 넣다가 "maxHeap의 루트 > minHeap의 루트"일 때가 오면 루트끼리 swap하면 됨!!

아래 예시를 보면서 이해해보자.

 

수빈이가 5, 4, 3, 2라는 4개의 숫자를 외쳤다고 하면,

i	수빈이가 외친 숫자	maxHeap	minHeap
0	5	5
1	4	5	4
maxHeap의 루트(5) > minHeap의 루트(4) => 교환하기		4	5
2	3	3 4	5
3	2	3 4	5 2
maxHeap의 루트(4) > minHeap의 루트(2) => 교환하기		2 3	5 4

중간값을 출력하면 5 4 4 3이 나온다!!

 

위의 과정을 코드로 작성하면 이렇게 됨

---

코드 짜는 거 보다 설명하는 게 백만배 어려워......

 

자바 언어를 다 까먹은 줄 알았더니 정리해둔 거 보니까 다시 손이 막 움직임!!

덜덜덜 다행이다