[백준 2075] - N번째 큰 수(정렬) C++

문제

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

2075번: N번째 큰 수

접근방법

이 문제는 메모리를 신경써야하는 문제였다.

 

12mb면 12000byte인데, 무턱대고 2차원 배열 만들어버리면 메모리초과다.

따라서 입력을 받는 중간 중간 메모리를 정리해줘야한다.

 

priority_queue로 풀어도 되는데, vector로 푸는 게 더 빠를 거 같아서 vector를 썼다.

 

메모리가 제한되므로, 한 줄 받을 때마다 상위 5개 숫자빼고 다 배열에서 pop했다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

#define FOR(i, n) for(int i=0;i<n;i++) 
#define FASTERIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define MIN -1234567890

vector<int> table;
int n;
int main( ) {
    FASTERIO
    cin >> n;
    int num;
    table = vector<int>();
    FOR(i, n) {
        FOR(j, n) {
            cin >> num;
            table.push_back(num);
        }
        sort(table.begin(), table.end(), greater<>());
        while(table.size() > n) table.pop_back();
    }
    cout << table[n-1] << "\n";

    return 0;
}

개선할 점

문제의 의도가 뭔지를 빨리 파악할 수 있도록 연습해야한다.

 

이 문제가 시간효율을 달성하는 것에 포인트가 있는 지,

공간 효율을 달성하는 것에 포인트가 있는 지,

구현하는 것이 포인트인지,

특정 알고리즘을 이용하는 문제인지

 

포인트만 잘 짚으면 한 번에 통과할 수 있을 것이다.