KyungHyun Lim

ML/AI/SW Developer

BAEK-2075 N번째 큰수(C++)

Aug 20, 2021

Algorithm

1. 문제 설명

문제 링크
NxN 배열이 주어진다. 모든 수는 자신의 한 칸 위에 있는 수보다 크다. 이러한 표에서 N번 째 큰수는?

조건
1 <= N <= 1,500
수는 -10억 보다 크고 10억보다 작거나 같은 정수 -> int 범위

2. 풀이

priority_queue 라이브러리 활용
전체 수를 탐색하며 우선순위 큐에 N개의 원소만 남겨두기!

3. 코드

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<queue>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
    int N;	// NxN 의 맵 크기
    int num;// 맵의 각 칸의 수
    priority_queue<int, vector<int>, greater<int>> pq;
    
    cin >> N;// 맵크기 입력 받기

	// 맵의 숫자들 탐색
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            cin >> num; // 숫자 입력 받기
            pq.push(num); // 우선순위 큐에 입력

			// N보다 크면 pop() -> top()이 N번째 큰수가 된다.
            if(pq.size() > N) pq.pop(); 
        }
    }

    cout << pq.top() << endl;
    
    return 0;
}

4. 결과

간단한 문제라 생략!