백준 14235번 Pseudo code

문제 링크

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

14235번: 크리스마스 선물

 

시간 제한 / 메모리 제한

2 초

512 MB

 

문제

크리스마스에는 산타가 착한 아이들에게 선물을 나눠준다. 올해도 산타는 선물을 나눠주기 위해 많은 노력을 하고 있는데, 전세계를 돌아댕기며 착한 아이들에게 선물을 나눠줄 것이다. 하지만 산타의 썰매는 그렇게 크지 않기 때문에, 세계 곳곳에 거점들을 세워 그 곳을 방문하며 선물을 충전해 나갈 것이다. 또한, 착한 아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물해 줄 것이다.

이제 산타가 선물을 나눠줄 것이다. 차례대로 방문한 아이들과 거점지의 정보들이 주어졌을 때, 아이들에게 준 선물들의 가치들을 출력하시오. 만약 아이들에게 줄 선물이 없다면 -1을 출력하시오.

 

입력

첫 번째 줄에서는 아이들과 거점지를 방문한 횟수 n이 주어진다.(1≤n≤5,000)

다음 n줄에는 a가 들어오고, 그 다음 a개의 숫자가 들어온다. 이는 거점지에서 a개의 선물을 충전하는 것이고, 그 숫자들이 선물의 가치이다. 만약 a가 0이라면 거점지가 아닌 아이들을 만난 것이다. 선물의 가치는 100,000보다 작은 양의 정수이다.(1≤a≤100)

출력

a가 0일 때마다, 아이들에게 준 선물의 가치를 출력하시오. 만약 줄 선물이 없다면 -1을 출력하라. 적어도 하나의 출력이 있음을 보장한다.

예제 입력

5
0
2 3 2
0
0
0

예제 출력

-1
3
2
-1

 

문제 풀이를 위해 생각한 것

1. "아이들을 만날 때마다 자신이 들고있는 가장 가치가 큰 선물 하나를 선물" -> 만날 때마다 내림차순 정렬이 돼있어야 함
2. 최대 힙 자료구조를 사용할 수 있겠다.
3. 힙에 원소가 있으면 pop한 결과(가장 가치가 큰 선물)을 출력하고, 원소가 없으면 -1을 출력한다.
4. 거점지에 도착하면 a개의 선물을 힙에 추가한다.

 

사용한 자료구조

최대힙.

아이들을 만날 때마다 최대 가치의 선물을 줘야 한다.

 

풀이 코드

n = 첫 입력값을 정수로
mh = 최대힙 선언

n번 동안:
	a = 입력값을 정수로
	if a == 0: # 아이들
		if mh에 원소가 있으면:
			print mh.pop()
		elif mh에 원소가 없으면:
			print -1
	elif a != 0: # 거점
		mh.append(a를 제외한 입력값)

 

시간 복잡도 분석

O(NlogN).

a개의 원소를 최대 N - 1번 heap에 push(최소 한 번의 출력은 보장)하고, 최대 N번 pop한다.

힙의 push, pop 연산은 모두 O(logN)이다.

-> O(a(N-1)logN)

 

최대차항의 계수를 제외하면

본 알고리즘의 시간 복잡도는 O(NlogN)이다.

 

문제에서 중요한 부분

매 아이들을 만나는 순간마다 최대 값을 출력해야 하기 때문에,

최대힙을 사용하면 정렬에 O(NlogN), push, pop에 O(logN)아 소요되어 시간 효율적인 알고리즘을 만들 수 있다.