개요

백준2075:N번째 큰 수

• 입력
  첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

• 출력
  첫째 줄에 N번째 큰 수를 출력한다.

접근 방식

1. 처음엔 단순히 시간복잡도만 생각하여,
   1500* 1500정도의 연산이면 시간제한에 안 걸리겠구나라고 생각했다.

2. 그후 우선순위 큐에 모든 값을 집어넣고 N번째 값을 꺼내는식으로 구현했지만 문제에서 메모리제한이 12MB인 관계로,
   당연히 메모리 초과가 나왔다.

3. 따라서 우선순위 큐의 사이즈를 N으로 정해두고 사이즈가 더 커지면 pop시켜주는 식으로 N으로 유지했다.

전체 코드

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

priority_queue<int, vector<int>, greater<int>> pq;

void Input() {

	int N=0,tmp=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> tmp;
			//우선순위큐가 비어있거나, 새로 입력받는 값이 pq.top값보다 클때
			if (pq.empty() || tmp > pq.top()) {
				//만약 pq의 사이즈가 N개일때는 pop해준다
				if (pq.size() == N)
					pq.pop();
				//N개가 아닐땐 push
				pq.push(tmp);
			}

		}
	}

	cout << pq.top();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	Input();
}

문풀후생

사실 문제들이 대부분 메모리 제한을 128MB 이렇게 넉넉하게 줘서
자주 생각해볼일이 없던 메모리 제한을 다시 상기하게 해준 문제였다.