https://www.acmicpc.net/problem/2075
문제
> N×N의 표에 수 N2개 채워져 있다.
> 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다.
> 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개의 수만 다뤄주면서 서로비교한다.
기본적으로 최소힙이므로 peek, 맨앞엔 가장 작은 값이 들어가고 점차 큰 값이 들어있다.
N개만 따져주는 이유는 문제에서 N번째로 큰 수를 원하기 때문이다. 즉 모든 수를 비교하고 난 후엔 peek에 우리가 원하는 N번째로 큰 수가 있다.
우선순위 큐의 크기가 N보다 작으면 일단 다 입력받고 N이 찼으면 이제 peek에 있는 제일 작은 값과 새로 들어올 수를 비교해 넣을지 말지 정한다.
문제해결
> N을 입력받고 NxN으로 표가 들어오므로 한 행 씩 N번 입력받는다.
> while문으로 한 행의 수들을 토큰으로 받아 처리한다.
> 우선순위 큐 pq에 수를 N개 들어올 때 까지 입력받는다.
> N개가 넘어가면 peek에 있는 가장 작은 수와 새로 들어온 num과 비교한다.
> num이 peek보다 작다면 쓸모가 없으므로 넘어가고 크면 peek가 쓸모가 없어지므로 poll로 지우고 offer로 넣어준다.
> 우선 순위 큐이므로 offer로 넣으면 알아서 정렬이 된다.
> 모든 수의 비교가 끝난 뒤 peek에 있는 수는 NxN개의 수 들 중 N번째로 작은 수가 된다. 이를 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//2075번 N번째 큰 수
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
while(st.hasMoreTokens()) {
if(pq.size() < N) pq.offer(Integer.parseInt(st.nextToken()));
else {
int num = Integer.parseInt(st.nextToken());
if(pq.peek() < num) {
pq.poll();
pq.offer(num);
}
}
}
}
System.out.print(pq.peek());
}
}
후기
최악의 경우 2,250,000개의 수를 입력받는데 이 모든 수를 우선순위 큐에서 정렬하면 시간초과가 날 수 있을 것 같았다. 그래서 N개만 필요하므로 N개 씩 잘라서 따져줬다.
