[BOJ 2075] N번째 큰수

문제 : N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다.
표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

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

2075번: N번째 큰 수

주의 사항

• 표에서 모든 수는 자신의 한 칸 위에 있는 수보다 크다.

문제 분석

• 표에서 각 열의 수들은 각 밑으로 갈 수록 점점 커진다. 이를 이용하여 입력값과 표의 크기에 따라 각 행에 있는 수들로 구해 보려 했다.그러다가 어찌됐던 수들이 입력 되고 그 수들중 n번째로 큰 수만 찾으면 된다는 생각이 들었다.
• 우선순위 큐를 구현하여 배열에 내림차순으로 정렬하고 n번째값을 출력하면 되겠다는 생각을 했다. 

vector<int>arr;
int t,n,v;
class heap{
public:
    heap(){
        arr.push_back(0);
    }
    void swap(int idx1, int idx2){
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
    void upHeap(int idx){
        if(idx<=1) return;
        else {
            int parIdx = idx/2;
            if (arr[idx]>arr[parIdx]){
                swap(idx,parIdx);
                upHeap(parIdx);
            }
        }
    }
    void insert(int x){
        if(arr.size()>=1501){
            arr.pop_back();
        }
        arr.push_back(x);
        upHeap(arr.size()-1);
    }
};
int main(){
    cin>>n;
    heap h;
    t = n*n;
    while(t--){
        cin>>v;
        h.insert(v);
    }
    cout<<arr[n]<<endl;
}

효율적인 우선순위 큐 구현을 위해 heap을 구현해 문제를 풀어봤다.
다시보니 정말 바보같다. heap은 우선순위 '큐' 이지 우선순위 리스트가 아니다.
top에는 가장 우선순위가 높은 값이 들어있지만 그렇다고 모든 값이 우선순위에 맞게 정렬되어 있는 것은 아니다.
또, 다시보니 위 heap은 힙이라고 할 수도 없는 것이 pop과 downheap은 구현해 놓지도 않았다.
애초에 우선순위 큐는 search가 없다.ㅡㅡ

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>>pq;
int t,n,v;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    t=n*n;
    while(t--){
        cin>>v;
        pq.push(v);
        if(pq.size()>n) pq.pop();//size가 n보다 커지면 가장 작은값을 pop한다.
    }
    cout<<pq.top()<<endl;
    //pq의 size를 n으로 맞춰놨기 때문에 가장 작은값을 출력하면 n번째 큰수가 출력된다.
}

그러다 queue라이브러리의 priority_queue라는 stl을 알게되었고, 이를 이용해 문제를 풀었더니 금방 풀렸다.

#include <iostream>
#include <vector>
using namespace std;

int t,n,v;
class heap{
    vector<int>pq;
public:
    heap(){pq.push_back(0);}
    int size(){return pq.size()-1;}
    void swap(int idx1,int idx2){
        int tmp=pq[idx1];
        pq[idx1]=pq[idx2];
        pq[idx2]=tmp;
    }
    void upHeap(int idx){
        if(idx<=1) return;
        int parIdx=idx/2;
        if(pq[parIdx]>pq[idx]){
            swap(parIdx,idx);
            upHeap(parIdx);
        }
    }
    void downHeap(int idx){
        int left = 2*idx;
        int right = 2*idx+1;
        int child;
        if(left>size()) return;
        else if(left == size())child = left;
        else{
            if(pq[left]<pq[right]) child = left;
            else child = right;
        }
        if(pq[child]<pq[idx]){
            swap(child,idx);
            downHeap(child);
        }
    }
    void insert(int x){
        pq.push_back(x);
        upHeap(size());
    }
    int pop(){
        int top;
        if(size()==0) return -1;
        top = pq[1];
        swap(1,size());
        pq.pop_back();
        downHeap(1);
        return top;
    }
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    heap h;
    cin>>n;
    t=n*n;

    while(t--){
        cin>>v;
        h.insert(v);
        if(h.size()>n)h.pop();
    }
    cout<<h.pop()<<endl;
}

이번엔 우선순위 큐를 직접 구현해 보았다. 원래 구현했던 heap에 몇가지 기능을 더해 정확하게 구현했다. 이를 이용해서 stl을 이용했을 때와 같은 논리로 문제를 풀었고 이번에도 "맞았습니다"를 띄웠다.

시간복잡도

• (여기서 n은 입력값의 개수가 아닌 위에서의 n),사이즈가 커질때 마다 pop을 해줌
• 삽입-> O(logn)
• pop-> O(logn)
• n^2 반복
  ☞ O(n^2*logn)

느낀점

• heap,우선순위 큐에 대해 정확히 이해를 못하고 있던게 아닌가 하며 반성을 하게 되었다.
• 지금보니 정말 쉬운 문젠데 너무 오래걸린거 같다.
• 문제를 보고 배열을 내림차순으로 정렬해 n번째 값을 출력하려 했었다. <sort>를 쓰면 쉽게 풀 수 있을 것 같다. 다만 그게 더 효율적이진 않을거 같다.