문제

BOJ 2075, N번째 큰 수

핵심

• 입력의 크기가 $10^3$이라 대략 $O(N^2)$ 이하 알고리즘을 사용한다.
• 얼핏 보면 이게 문제야? 라는 생각이 든다. 덜컥 최대 힙 구현하고 모든 값을 추가한 다음 N번째 큰 수를 구해야 하니 N-1번 POP 하면 되겠구나 라고 생각할 수 있다.('-') 이렇게 구현할 경우 $1500^2$ * 4byte 대략 1000MB가 넘어 메모리 초과가 된다.
• 그렇다면 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 성질을 이용해서 넉넉하게 $N * N - 2 * N$부터 입력을 받으면 되지 않을까? N이 5라면 15부터 입력을 받으면 되게끔 말이다. 하지만 이 방식도 예외가 있다. 특정 열에서만 숫자가 굉장히 크고, 나머지 열은 굉장히 작은 수라면 특정 열이 0 ~ n번까지 필요할 수 있다.
• 따라서 직관과 조금 다르게 최소힙을 구현하여 크기를 N으로 유지하면 되지 않을까? 어떤 수가 들어온다면, 큐에서 가장 작은 값을 빼는 식으로 말이다. 이렇게 구현한 결과는 아래와 같다.

개선

코드

시간복잡도

• $O(N^2 * log2N)$

C++

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

int n;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	auto comp = [](auto& a, auto& b) { return a > b; };
	priority_queue<int, vector<int>, decltype(comp)> pq(comp);
	cin >> n;
	for (int i = 0; i < n * n; ++i) {
		int num;
		cin >> num;
		pq.push(num);
		if ((int)pq.size() > n)
			pq.pop();
	}
	cout << pq.top() << '\n';
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int num = Integer.parseInt(st.nextToken());
                pq.add(num);
                if (pq.size() > n)
                    pq.poll();
            }
        }
        System.out.println(pq.peek());
    }
}