문제

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

접근

처음에 문제보고 그냥 배열에 담아 sort해서 N번째 큰 수 찾으면 되는거 아닌가? 생각했는데
요 메모리 제한이 있었다.
그럼 배열을 선언하지 않고 바로 우선순위 큐에 담으면 되나? 했는데 역시 메모리 초과가 발생했다.

문제를 다시 보니 모든 수는 자신의 한 칸 위에 있는 수보다 크다라는 조건이 있었다.

이걸 보고 자료구조의 크기를 관리할 수 있겠다는 생각을 했다.

최소힙으로 데이터를 하나씩 저장하는데 데이터가 N개보다 클 때 pop을 해주면 힙에는 계속 N개의 데이터가 저장되어 있고 마지막에는 크기가 가장 큰 수 ~ N번째로 큰 수만 저장되어 있다.
따라서 Q.top()을 출력해주면 N번 째 큰 수를 구할 수 있다.

이렇게 로직을 작성하여 제출했는데 시간 초과가 떴다.

ios::sync_with_stdio(0);
cin.tie(0);

붙여주니 통과되었다.

코드

#include<bits/stdc++.h>
using namespace std;

priority_queue<int, vector<int>,greater<int>> Q;
int N;

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;	

	int num;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {			
			cin >> num;

			Q.push(num);
			if (Q.size() > N)
				Q.pop();
		}
	}

	cout << Q.top();
	

	return 0;
}