BOJ 2075

N번째큰수

문제출처

1.설계(5)

• 문제 해석

  • N*N 배열에서 N번째 큰 수를 찾는 문제입니다.
  • 모든 수는 자신의 한칸 위에 있는 수보다 큽니다.

• 설계

  • 메모리 제한이 10MB로 아주 작아서, N*N(N<=1500)배열을 담아서 풀지 못하도록 유도한 것 같습니다.
  • 우선순위 큐(최소힙)를 이용하여 대소비교를 N*N번 합니다.
  • 메모리 제한으로 큐에 N*N개를 담을 수 없기 때문에, 큐에 N개의 숫자만 저장하도록 합니다.

2.구현(30)

• 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;

priority_queue<int> pq;

int N;

int main() {

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

• 디버깅

  • 배열을 이용하면 메모리 제한으로 간당간당하게 걸릴 것 같아 시도해보았으나, 메모리 초과가 나왔습니다.

• 제출결과

564ms

3.마무리

• 코딩테스트를 준비하는데에 있어서 메모리 제한을 고려하는 문제가 그리 많지 않습니다.
  이러한 문제를 통해 메모리 또한 고려해야 할 것을 실감하였습니다.