본문 바로가기

알고리즘 관련/BOJ

BOJ)2075 N번째 큰 수

문제:icpc.me/2075


N^2개의 수가 들어올 때 N번째로 큰 수를 구하는 문제이다.


N이 최대 1500 밖에 안들어오므로 단순히 값을 다 받아서 정렬해주는 N^2logN의 해법으로 해결할 수 있다.


하지만 메모리제한이 10MB이므로 힙을 이용하여 수를 받을 때 마다 큰 수 N개만큼만 저장해주고 그 수들중 가장 작은 수와 들어오는 수를 비교를하여 힙을 관리해주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, x;
priority_queue<int> pq;
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n*n; i++) {
        scanf("%d"&x);
        if (pq.size() < n)
            pq.push(-x);
        else {
            if (-pq.top() < x) {
                pq.pop();
                pq.push(-x);
            }
            else
                continue;
        }
    }
    printf("%d\n"-pq.top());
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1745 숨기  (0) 2017.03.29
BOJ)5397 키로거  (0) 2017.03.28
BOJ)1326 폴짝폴짝  (0) 2017.03.26
BOJ)13166 범죄 파티  (0) 2017.03.25
BOJ)3736 System Engineer  (0) 2017.03.25