[BaekJoon 2075번] N번째 큰 수(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

2075번: N번째 큰 수

 

 

[문제 설명]

 

 

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=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

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

 

 

[입력]

 

 

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

 

 

[출력]

 

 

첫째 줄에 N번째 큰 수를 출력한다.

 

 

[입출력 예]

 

 

입력	출력
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	35

 

 

[문제 풀이]

 

C++의 경우 메모리가 12MB 로 제한되어 있는 문제라 메모리 초과에 주의해야한다.

 

N번째 큰 수를 출력하는 문제인데, 여기서 작은 값이 앞에 오도록 하는 우선 순위 큐(최소 힙)을 사용했다.

그리고 메모리 제한 때문에

1. 우선 순위 큐의 사이즈가 N보다 작은 경우엔 입력으로 들어온 값을 push해주었다.

 

2. 우선 순위 큐의 사이즈가 N보다 큰 경우엔

2-1. 우선 순위 큐의 top이 입력으로 들어온 값보다 작은 경우

2-1-1. 우선 순위 큐를 pop해주고, 입력으로 들어온 값을 push해주었다.

 

위 방법대로 코드를 작성하면 우선 순위 큐의 사이즈는 N이고, 현재 우선 순위 큐의 top()이 N번째 큰수가 된다.

 

실시간으로 정렬이 필요할땐 '우선 순위 큐' 자료 구조를 사용한다.

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>

using namespace std;
priority_queue<int, vector<int>, greater<int>> pq;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            int n; cin >> n;
            if(!pq.empty()) {
                int qSize = pq.size();
                if(qSize < N) {
                    pq.push(n);
                } else {
                    if(pq.top() < n) {
                        pq.pop();
                        pq.push(n);
                    }
                }
            } else {
                pq.push(n);
            }
        }
    }
    
    cout << pq.top() << '\n';
    return 0;
}