BOJ - 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번째 큰 수를 출력한다.

예제 입력 1 
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
예제 출력 1 
35
출처

사용할 자료구조

두가지 방식으로 풀어봤습니다.

1- N개의 스택을 사용하여 그 스택중들 중에서 가장 큰 수를 하나씩 pop해가며 N번째 수를 찾는 방식

2-우선순위큐(min heap)에 N개만큼 유지해나가며 작은 수는 삭제하고 큰 수는 삽입하는 방식

풀이 과정

<스택을 사용한 풀이>

• 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이라는 문제의 설명이 있으므로, 스택 배열을 만들어 각 배열의 순서대로 삽입하면 가장 큰 것이 top에 있습니다.
• 다음 각 스택의 top을 비교하면서 어떤 스택이 N번째로 큰지 찾으면 됩니다.

<우선순위 큐를 사용한 풀이>

• 모든 수를 우선순위큐(min heap)에 넣어서 N번째로 큰 수를 찾으면 됩니다,
• 그러나 모든 수를 넣게 되면 메모리 초과가 일어나게 되므로, 우선순위큐에 N개 만큼 쌓였을 때, 가장 작은 수 (우선순위큐의 top)를 pop해줍니다,.
• 마지막에는 우선순위큐에 가장 큰 수부터 N개만 남게됩니다. (top이 N번째 큰수)

시간 복잡도

<스택을 사용한 풀이의 시간 복잡도>

스택의 삽입/삭제 연산 O(1)입니다.

아래 코드와 같이 두개의 N만큼의 루프를 돌며 삽입/삭제 연산을 하므로 시간복잡도는 O(N^2)입니다.

    for(int i=0;i<n-1;i++){

        int max = st[0].top();
        int index = 0;
        for(int j=1;j<n;j++){
            if(max<st[j].top()){
                max = st[j].top();
                index = j;
            }
        }

        st[index].pop();
    }

<우선순위 큐를 사용한 풀이의 시간 복잡도>

우선순위큐의 삽입/삭제 연산은 O(logN)입니다.

NN만큼 루프를 돌며 삽입/삭제 연산을 수행하므로 *O(N^2longN)**입니다.

스택을 사용한 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    stack<int> st[n];
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int n;
            cin>>n;
            st[j].push(n);
        }
    }
    for(int i=0;i<n-1;i++){

        int max = st[0].top();
        int index = 0;
        for(int j=1;j<n;j++){
            if(max<st[j].top()){
                max = st[j].top();
                index = j;
            }
        }

        st[index].pop();
    }
    int answer = st[0].top();
    for(int i=1;i<n;i++){
        if(st[i].top()>answer){
            answer=st[i].top();
        }
    }
    cout<<answer;


    return 0;
}

우선순위큐를 사용한 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <map>
#include <functional>
using namespace std;

int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    priority_queue<int,vector<int>,greater<>> pq;
    for(int i=0;i<n*n;i++){
         int num;
         cin>>num;
         if(pq.size()<n){
             pq.push(num);
         }else if(pq.top()<num){
             pq.pop();
             pq.push(num);
         }
     }

    cout<<pq.top();

    return 0;
}