[BaekJoon/백준] 2075번: N번째 큰 수(C/C++)

백준 2075번: N번째 큰 수

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

2075번: N번째 큰 수

---

문제 설명

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

---

접근 방법

이번 문제는 정수 N을 입력받고, N^2개의 정수를 입력받아 N번째 큰 수를 출력하는 문제다.

우선순위 큐(Priority Queue, 이하 PQ)를 사용하면 입력 받은 수를 정렬해서 큰 수부터 순서대로 출력할 수 있으므로 쉽게 풀 수 있다. 처음에는 큰 수부터 출력하면 그냥 다 입력받고 N-1번 pop하고 top을 출력하면 되겠거니 생각하고 문제를 풀었으나 메모리 초과가 발생했다.

그래서 고민하던 중 마이너스를 활용해 PQ를 뒤집어 큰 수부터 보관하는 방식을 알아내서 문제를 해결했다. 마이너스를 활용하면 가장 큰 수는 가장 작은 수가 된다. 따라서 PQ의 size를 N을 초과하지 않게한다면 가장 큰 수~N번째 큰 수까지 보관되어 메모리를 효율적으로 사용할 수 있고, 출력시 top값에 마이너스를 붙여서 출력하면 해결할 수 있다.

---

코드

• 처음 코드(메모리 초과로 실패)

#include <stdio.h>
#include <queue>
using namespace std;

int main(int argc, char*argv[]) {
	int N, M;
	priority_queue<int> pq;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &M);
			pq.push(M);
		}
	}

	for (int i = 0; i < N-1; i++)
		pq.pop();

	printf("%d\n", pq.top());
	return 0;
}

• 완성 코드(성공)

#include <stdio.h>
#include <queue>
using namespace std;

int main(int argc, char*argv[]) {
	int N, M;
	priority_queue<int> pq;

	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &M);
			pq.push(-M);
			if (pq.size() > N)
				pq.pop();
		}
	}

	printf("%d\n", pq.top());
	return 0;
}

---

결과

백준 제출 결과