[BAEKJOON] 2075번 N번째 큰 수

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

문제조건

1. N×N의 표에서 N번째 큰 수를 구해라.
2. 모든 수는 자신의 칸(행)보다 위에 있는 수보다 크다.

접근방법

 

접근방법이라 할것도 없었고, 입력받고 냅다 내림차순정렬해서 N번째 순서의 숫자를 찾았다.

 

이렇게 되어버린,,

메모리초과는 잘 나지 않아서 당황했지만 어디서 생긴걸까 생각해보면 1500 x 1500 x 4(Byte) = 대략 9MB여서 메모리에 대해서는 아예 초과가 안날줄 알았지만, 내부적으로 사용되는 변수, 내가 사용하는 또 다른 변수들을 고려한다면, 아리까리한 메모리라는 것이다. 일단 해결하기 위해선, 입력으로 받는 표에 대해 전부 저장하면 안된다는것이다.

 

풀이

 

배열, 벡터, 큐 등 어떤 자료구조 하나를 선택하고, 그것의 크기가 N보다 커지면 계속 정렬해주는 식으로 하면 메모리는 조건을 만족할 것이다. 단 <algorithm> 헤더에 있는 sort함수를 쓴다면 시간복잡도 O(n log n) 으로 N*N에서 이것을 반복하는 것은 시간초과가 난다. 그래서 나는 O(log n) 의 시간복잡도를 갖는 우선순위 큐를 선택했다. 최소힙으로 값들을 유지하면서 우선순위 큐의 루트노드가 N번째 큰수가 된다.

 

소스코드

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

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	int a;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a;
			pq.push(a);
			if (pq.size() > n) pq.pop();
		}
	}
	cout << pq.top();
}