[PS] 백준 #2075 N번째 큰 수 문제풀이
[ 문제 풀이 ]
- Problem : 백준 #2075
- 구분 : DS, PQ(우선순위 큐)
- 난이도 : Gold 4
- 풀이 방법 :
- 우선순위 큐를 사용하면 푸는 방법은 여러가지가 있는데, 주어진 메모리가 12MB로 작기 때문에 N*N인 수를 모두 우선순위 큐에 넣고 돌리면 메모리 초과가 발생합니다.
- 따라서, 최소힙 구조를 한 우선순위 큐의 front에 위치한 값보다 클 경우에만 input 값을 넣어주고 n개 이상의 값이 들어오면 front 값을 pop 해주면서 n번째 큰 값을 front 위치에 유지시켜 답을 구할 수 있습니다.(단, queue가 비어있을 때는 무조건 넣어줍니다.)
- 시간 복잡도는
O(N^2logN)
입니다.
[ 🤟🏻 Code from ss-won ]
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, input;
priority_queue<int, vector<int>, greater<int>> mnq;
int main() {
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for(int i=0;i<n*n;i++){
cin >> input;
mnq.push(input);
if(mnq.size() > n)
mnq.pop();
}
cout << mnq.top();
return 0;
}
Author And Source
이 문제에 관하여([PS] 백준 #2075 N번째 큰 수 문제풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ss-won/PS-백준-2075-N번째-큰-수-문제풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)