백준 2075 - N번째 큰 수

Java

2075 번 - N번째 큰 수

문제

접근 방법

입력으로 주어지는 수의 개수가 N(1 ≤ N ≤ 1,500)으로 N x N = 2,250,000으로 꽤 크다.
따라서 모든 수를 저장하면 안된다.

문제를 자세히 보면 N번째 큰 수를 구하라고 되어있다.
이 말은 즉, N개의 수만 저장하여, 입력으로 들어오는 수를 하나씩 대소를 비교하여 수를 바꿔주는 방법으로 해결하면 된다.

따라서, 자동으로 정렬해 주는 PrioirtyQueue를 사용하였는데,
처음으로 주어지는 첫 줄 N개의 수를 일단 저장한다.
이후 2번째 줄부터 N번째 줄까지 각 수를 하나씩 PQ의 최소 값을 비교하여 만약 더 크면, 가장 작은 수를 제거하고 현재 수를 넣는다.

이를 N번째 줄까지 반복하면 PQ의 첫 번째, 즉 가장 작은 수가 N번째로 큰 수가 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, result;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	n = stoi(br.readLine());

    	PriorityQueue<Integer> pq = new PriorityQueue<>();


    	int num;
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
			// 첫번째 줄일 때, N개만큼 값을 받는다.
    		if(i == 0) {
    			for(int j = 0; j < n; j++)
    				pq.add(stoi(stk.nextToken()));
    		}
			// 이후 하나씩 확인하여 pq의 최소 값보다 크면, 가장 작은 것 하나를 버리며 추가
    		else {
    			for(int j = 0; j < n; j++) {
	    			num = stoi(stk.nextToken());
	    			if(pq.peek() < num) {
	    				pq.poll();
	    				pq.add(num);
	    			}
    			}
    		}
    	}

    	System.out.println(pq.peek());
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

흰트를 보고 깨달은 문제

개선할 점