[백준] 골드5 : (11509) 풍선 맞추기

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

 

문제 자체는 간단한데, 입력이 최대 1,000,000개 들어올 수 있다는 점이 문제이다.

시간초과가 나지 않으려면 전체 입력의 순회를 1~2회 안에 끝내야 한다. (순회 내부에서도 로직이 있기 때문에)

 

해시 맵을 통해 높이 n에 풍선이 몇 개 있는지 저장한다. (그냥 100만 개 배열로 해도 무방)

각 화살이 지나간 위치를 큐로 저장한다. (화살의 높이가 변경될 때마다 업데이트)

 

풍선을 순서대로 입력받으며 모든 화살을 동시에 쏜다고 가정한다.

풍선이 하나 띄워질 때 마다 큐에 화살 하나를 추가한다. (무조건 해당 풍선을 어떤 화살이든 터트려야 하기 때문)

 

현재 풍선보다 1칸 높은 풍선이 있다면, 해시 맵에 풍선 높이를 업데이트한다. (이전 높이 풍선 -1, 현재 높이 풍선 +1)

큐를 업데이트 한다. (이전 높이 풍선을 기준으로 큐에 화살이 들어가 있으니, 이를 현재 높이로 업데이트)

#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N = 0;
	cin >> N;

	// 높이 n에 떠있는 풍선 개수
	unordered_map<int, int> Ballon;

	// 화살 위치
	queue<int> Answer;

	for (int i = 0, j; i < N; ++i)
	{
		cin >> j;
		
		// 현재 풍선보다 1칸 높은 풍선이 이전에 있었다면,
		// 그 풍선을 터트리고 현재 풍선까지 터트릴 수 있음
		if (Ballon[j + 1] > 0)
		{
			Ballon[j + 1]--;	// 1칸 높은 풍선 -1
			Answer.pop();		// 화살 제거
		}
		Ballon[j]++;
		Answer.push(j); // 현재 높이로 화살 추가
	}

	cout << Answer.size() << '\n';
}