[백준]2325번: 자료구조는 정말 최고

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

23253번: 자료구조는 정말 최고야

 

처음 이 문제를 풀때 더미의 순서를 일정하게 유지하는 부분이 힘들었다. 이에 다양한 접근법을 시도하면서 vector를 통해 해결했다.

 

접근 방법

1) 우선 순위 큐를 선언한다. 이때 오름차순으로 정렬될 수 있게 설정한다.

2) 우선 순위 큐에 해당 책과 어느 더미 몇 번째에 위치하는지 저장한다.

3) lis라는 vector를 통해 각 더미의 현재 위치를 추적하는데 사용한다. 즉 lis의 각 요소 해당 더미의 현재 위치를 나타내며 이는 우선 순위 큐에서 추출된 요소의 위치와 일치하는지 아닌지 판단한다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

#define FastIO ios::sync_with_stdio(false); std::cin.tie(NULL); std::cout.tie(NULL);

using namespace std;

int main(void)
{
	FastIO;
	
	int N = 0, M = 0; // N권 교과서, 더미 M개
	cin >> N >> M;
	int K = 0; // 더미 개수 K
	priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> pq;
	vector<int> lis(M, 0);

	for (int i = 0; i < M; i++)
	{
		int temp = 0;
		cin >> K;
		for (int j = K-1; 0 <= j; j--)
		{
			cin >> temp;
			pq.push(make_pair(temp, make_pair(i, j)));
		}
	}
	
	while (!pq.empty())
	{
		pair<int, pair<int, int>> tmpPair = pq.top();
		pq.pop();
		if (lis[tmpPair.second.first]++ != tmpPair.second.second) 
		{
			cout << "No" << "\n";
			return 0;
		}
	}
	cout << "Yes" << "\n";
	return 0;
}