백준 (1655) - 가운데를 말해요[우선순위 큐]

✅ 1. 문제 설명

• 정수가 하나씩 순서대로 주어짐
• 매 입력마다 지금까지 등장한 모든 수 중 "중간값"을 출력
  • 짝수개라면 두 중간 중 더 작은 값
• 예시:
  • 입력: 1, 5, 2, 10, -99, 7, 5
  • 출력: 1, 1, 2, 2, 2, 2, 5

 

---

✅ 2. 중간값(중위값)란?

• 정렬된 수열에서 한가운데에 위치한 값
• 짝수개라면 두 가운데 중 "작은 값"
• 예시:
  • [2, 5, 7] → 5 (가운데)
  • [1, 2, 3, 4] → 2 (두 가운데 중 작은 값)

 

---

✅ 3. 효율적인 풀이법: 두 개의 우선순위 큐(힙)

• 최대힙(left): 중간값 이하의 값 저장
• 최소힙(right): 중간값 이상의 값 저장
• 항상 "최대힙의 루트"가 현재 중간값이 됨
  • left.size() == right.size() 혹은 left가 1 더 많게 유지

 

---

✅ 그림으로 원리 요약

left(최대힙): [중간값 이하]    right(최소힙): [중간값 초과]
         ↓
     [중간값]

• 홀수개 → left의 루트가 중간값
• 짝수개 → left의 루트(작은 쪽 중간 값)

 

---

✅ 4. Java 코드 (BufferedReader + StringBuilder 최적화)

import java.io.*
import java.util.*

public class Main {
	public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        // 최대 힙(중간값 이하), 최소 힙(중간값 초과)
        PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> right = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        
        for (int i = 1; i <= N; i++) {
        	int num = Integer.parseInt(br.readLine());
            
            left.offer(num);
            
            // 두 힙이 있다면, left의 최대값 > right의 최소값이면 swap
            if (!right.isEmpty()  && left.peak() > right.peak()) {
            	right.offer(left.poll());
                left.offer(right.poll());
            }
            
            // left가 항상 right보다 1 많거나 같게 유지
            if (left.size() > right.size() + 1) {
            	right.offer(left.poll());
            }
            
            sb.append(left.peak()).append("\n");
         }
         System.out.pring(sb);
    }
}

 

---

✅ 5. 예시 입력/출력

입력

7 # 입력개수
1
5
2
10
-99
7
5

 

출력

1
1
2
2
2
2
5

 

---

✅ 6. 시간복잡도 & 팁

• 매 입력마다 0(logN)
• 입력/출력 속도까지 최적화 ( BufferedReader, StringBuilder 사용)
• 일반 리스트+정렬은 시간초과 → 힙 두 개로 효율적 구현!
• 실전 코딩테스트, 알고리즘 대회에서 정말 많이 쓰이는 패턴

 

---

✅ 7. 정리 및 실전 노트

• "실시간 중간값" = 두 힙(최대힙/최소힙)
• 입력/출력 빠르게 (I/O 최적화)
• "짝수개면 두 가운데 중 작은 값" 규칙만 주의