[BOJ] 백준 2075번 N번째 큰 수 (Java)

#2075 N번째 큰 수

난이도 : 골드 5

유형 : 자료구조 / 슬라이딩 윈도우 / 우선순위 큐 

2075번: N번째 큰 수

▸ 문제

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(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

▸ 출력

첫째 줄에 N번째 큰 수를 출력한다.

 

문제 풀이  

우선순위 큐는 기본적으로 오름차순으로 데이터를 정렬해주기 때문에 이를 이용하여 슬라이딩 윈도우 알고리즘에 적용하여 풀이를 하면 된다.  

 

데이터를 차례대로 입력받아 큐의 사이즈가 N에 도달했을 때, 새로 들어온 값과 큐에 들어있는 가장 작은 값(q.peek())을 비교하여 새로 들어온 값이 더 클 경우 데이터를 교체해주는 방식이다. 이는 구간 N만 탐색하여 계산이 가능하므로 시간복잡도 O(N)을 가진다.

 

그리고 큐의 최대 사이즈는 N으로 계속해서 데이터를 삭제, 삽입 해주므로 모든 데이터 N^2을 저장하여 정렬하는 방식보다 공간복잡도의 효율을 높여줄 수 있다.

 

구상

1. 우선순위 큐에 숫자를 담는다.
2. 큐의 사이즈가 n이 되면 맨 앞의 숫자(n개의 수 중 가장 작은 숫자)와 새로운 값을 비교한다.
   1. 새로운 값이 더 클 경우 데이터를 바꿔준다.
   2. 새로운 값이 작을 경우 그대로 유지한다.

 

풀이 코드

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

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