[C++ / 2075] N번째 큰 수

문제

2075번: N번째 큰 수

---

문제 설명

N×N의 표에 수 N²개 채워져 있다. 

채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다.

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번째 큰 수를 찾으면 되는 쉬운 문제이다. 

 

조금 신경을 써줬던 부분은 C++로 구현하는 데 있어서 우선순위 큐(Priority Queue) 자료구조 방식을 통해 해결한 점이다.

C++에서는 PQ를 다음과 같이 선언한다.

priority_queue<자료형, 구현체, 비교 연산자>
ex) priority_queue<int, vector<int>, greater<int>>

오름차순 구현을 위해 greater<int>라고 작성해두었지만, 기본적으론 less<int>이며 오름차순으로 나온다.

구현할때 참고한 블로그.

---

솔루션

#include <iostream>
#include <queue>

using namespace std;

void sol(int n)
{
  priority_queue<int, vector<int>, greater<int>> pq;
  int tmp;
  for (int i = 0; i < n * n; i++)
  {
    cin >> tmp;
    pq.push(tmp);
    if (pq.size() > n)
      pq.pop();
  }
  cout << pq.top();
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  cin >> n;
  sol(n);
}