[BAEKJOON] 1655 가운데를 말해요

문제 요약

• 알고리즘 분류: 힙, 우선순위 큐, 자료구조
• 난이도: Gold2
• 문제내용:
  • 숫자가 추가될때마다 정렬해서 가운데 숫자를 출력하면된다.

• 사이트: https://www.acmicpc.net/problem/1655

1655번: 가운데를 말해요

 

문제풀이

 이번 문제는 힙으로 풀어야 한다. 하지만 힙을 구하는 목적은 최대값, 최소값인데 중간 크기를 구하는 힙은 없어서 어느정도 생각해서 풀어야 될 문제이다. 힙 관련된 자세한 내용은 아래의 사이트에서 확인 헤보면된다.

https://jih3508.tistory.com/81

[알고리즘 이론] 힙(Heap)

문제 접근 방법

 이번 문제에서 큰 아이디어는 2개의 힙을 만들어서 왼쪽에는 최대값을 나타내는 힙 오른쪽은 최소값을 나타내는 힙으로 구현해서 값추가 할때마다 왼쪽 값중 최대값을 출력하면된다. 왼쪽은 최대값 오른쪽은 최소값은 어떻게 해야하는 구현 해야 할지는 그림으로 설명 하겠다.

1

5

2

10

-99

7

5

1, 5를 두개 힙으로 따로 표현 하겠다. 왼쪽은 최대값으로 오른쪽은 최소값으로 나타 낼수가 있다. 문제에서는 짝수개 일때 가운데는 작은 값으로 해야 하기 때문에 출력은 왼쪽 힙 구조로 해야 한다. 그럼 1, 5 추가 하면 1, 1이 나올 것이다.

 

2를 추가할때는 왼쪽 부터 2를 추가 한다. 힙정렬하면 위 그림 처럼 나온다. 그럼 출력 값은  2가 된다.

10을 추가도 왼쪽 부터 추가하면된다. 하지만 왼쪽 이랑 오른쪽 갯수 비교하면 왼쪽이 2개 더 많다. 그래서 10을 오른쪽으로 이동한다. 그럼 아래 그림 처럼 나온다.

 이번에도 출력 값은 2가 나온다.

-99, 7을 두개 추가를 했다. 위에 상황처럼 왼쪽이 2개 더 많아서 오른쪽으로 이동해야 한다. 이동한 결과는 아래 그림 처럼 된다.

위 결과대로 이번에도 출력값은 2가 된다.

5를 왼쪽에 추가하면 위 그림 처럼 되어서 5를 출력하면된다. 하지만 위에 대로 해도 중간이 왼쪽값이 오른쪽 값보다 클 경우가 있다. 그래서 마지막으로 비교해서 위치 바꾸기까지만 하면 정답이 된다. 위에 대로 구현 하면 (NlogN)이 되어서 시간초과 현상은 안나올것이다.

정리

1. 왼쪽 힙은 최대값 오른쪽 힙은 최소값으로 선언한다.
2. 왼쪽 부터 추가하고 오른쪽 길이가 2개 이상 나면 왼쪽 힙을 꺼내서 오른쪽에 추가한다.
3. 왼쪽 과 오른쪽 루트 노드랑 비교해서 왼쪽 루트노드가 크면 오른쪽이랑 바꿔 준다.

Code

Python

heapq 라이브러리 사용하면 heqp구현이 쉬워 진다.

import heapq, sys
input = sys.stdin.readline

lheap = [] # 작은 숫자 힙
rheap = [] # 큰 숫자 힙

for _ in range(int(input())):
    num = int(input())
    heapq.heappush(lheap, (-num, num))
    
    # 길이가 안맞을때 왼쪽 힙 큰 값을 오르쪽 힙에 추가한다.
    if len(lheap) - 1> len(rheap):
        heapq.heappush(rheap, heapq.heappop(lheap)[1])
    
    # 왼쪽 힙과 오른쪽 힙이 안맞을때 맞추는 작업
    if rheap and lheap[0][1] > rheap[0]:
        heapq.heappush(rheap, heapq.heappop(lheap)[1])
        num = heapq.heappop(rheap)
        heapq.heappush(lheap, (-num, num))
    
    print(lheap[0][1])

Java

 자바는 PriorityQueue를 사용해서 heap을 구현하면된다. 그리고 print로 출력하면 시간 초과로 떠서 StringBuilder로 출력해야 시간통과가 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

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> lheap = new PriorityQueue<Integer>(); // 작은 값 저장할 힙
		PriorityQueue<Integer> rheap = new PriorityQueue<Integer>(); // 큰 값 저장할 힙
		int num;
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			num = Integer.parseInt(br.readLine());
			lheap.add(-1 * num);
			// 길이가 안맞을때 왼쪽 힙 큰 값을 오르쪽 힙에 추가한다.
			if (lheap.size() - 1 > rheap.size()) {
				rheap.add(-1 * lheap.poll());
			}
			// 왼쪽 힙과 오른쪽 힙이 안맞을때 맞추는 작업
			if (!rheap.isEmpty() && (-1 * lheap.peek() > rheap.peek())) {
				rheap.add(-1 * lheap.poll());
				lheap.add(-1 * rheap.poll());
			}
			
			sb.append(-1 * lheap.peek()).append("\n");
		}
		System.out.println(sb);
	}
		
}