백준 2075 N번째 큰 수

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

 

서론

메모리 제한이 잡혀있다.

입력값을 전부 배열에 넣거나 큐에 넣으면 메모리초과가 발생할 것이다.

일부만 넣어야 한다.

 

아이디어

최소힙을 가지는 우선순위 큐를 만든 다음

큐에는 입력값 중 가장 큰 수 n개만 들어가도록 한다. 그럼 큐의 루트 힙이 정답이 될 것이다.

 

큐의 사이즈가 n개가 될때까지는 그냥 채워주고 n개가 되면 큐의 루트 힙보다 큰 값만 큐에 집어넣고 큐의 루트힙은 빼주면 된다. 그럼 입력값 중 가장 큰 수 n개가 들어있는 큐가 유지된다.

 

구현

//c++

#pragma warning(disable:4996)

#include <cstdio>
#include <queue>

int main() {
	std::priority_queue<int, std::vector<int>, std::greater<int>>q;
	int n;
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int x;
			scanf("%d", &x);
			int qSize = q.size();
			if (qSize < n) q.push(x);
			else if (x > q.top()) {
				q.push(x);
				q.pop();
			}
			else continue;
		}
	}

	printf("%d", q.top());
}