[BOJ] 2075 : N번째 큰 수 - travelbeeee

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

---

[알고리즘풀이]

메모리 제한이 10MB로 N * N 개의 수를 전부 저장한다음 Sorting하고 N번 째 큰 수를 출력한다면 '메모리 초과'를 받게 된다.

N * N 개의 수 중에서 N번 째로 큰 수를 출력하는 문제를 바꿔생각하면 들어온 입력 중 크기가 큰 순서대로 N개의 수만 기억하고 있으면 답을 출력할 수 있다.

즉, N개의 수를 N번 입력받으면서 지금까지 입력된 수 중에서 큰 순서대로 N개만 저장하는 알고리즘을 구현해야한다.

1차원 배열을 선언해서 문제를 해결할 수도 있지만, 자료구조 우선순위큐(Priority_Queue)를 이용하면 간단하게 알고리즘을 구현할 수 있다.

 

[예시]

-Input

5

12 7 9 15 5

13 8 11 19 6

21 10 26 31 16

48 14 28 35 25

52 20 32 41 49

-Priority_Queue

	PQ[0]	PQ[1]	PQ[2]	PQ[3]	PQ[4]
"12 7 9 15 5" 입력	5	7	9	12	15
"13 8 11 19 6" 입력	11	12	13	15	19
"21 10 26 31 16" 입력	16	19	21	26	31
"48 14 28 35 25" 입력	25	28	31	35	48
"52 20 32 41 49" 입력	35	41	48	49	52

-Output

35

 

[소스코드]

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

using namespace std;


int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int x,n;
	priority_queue<int, vector<int>, greater<int>> pq;
	cin >> n;
	for(int j = 0; j < n; j++){
		cin >> x;
		pq.push(x);
	}
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> x;
			if (x > pq.top()) {
				pq.pop();
				pq.push(x);
			}
		}
	}
	cout << pq.top();
}

---