[Java] BOJ2075, 백준 - N번째 큰 수

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	12MB	9235	3705	2514	39.760%

문제

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개가 될 때까지 채워주고, 큐의 사이즈가 N이 넘으면 피크값과 크기를 비교해서 숫자를 교체

풀이는 한줄이 끝

 

시간 제한 및 메모리 제한

N의 범위가 1500까지로 총 경우의 수의 범위는 1500*1500 = 2,250,000이다.

탐색은 한 번씩만 하면 되기 때문에 시간 제한에는 절대 안걸린다.

 

** 배열을 사용할 경우

하지만 배열을 사용할 경우 배열을 정렬해줘야 한다.

퀵 정렬을 이용하면 최악의 경우 O(N^2), N=2,250,000일 때.... 아무튼 시간 초과

- 메모리

배열의 메모리 4*1500*1500 = 9,000,000byte

퀵정렬 공간복잡도 = O(N*log(N)) = 약 천오백만byte

메모리 제한: 12MB = 12,582,912byte

메모리도 초과.

배열로는 절대못푼다.

 

 

**우선순위 큐를 사용하는 경우

우선순위 큐에 저장되는 최대 갯수도 N개이고,

비교도 우선순위 큐의 피크값과 입력받은 값의 0부터 N-1까지 한번씩만 비교해주면 된다.

입력받은 값을 전부 저장해줄 필요도 없다.

그러니 우선순위 큐를 사용해주도록 하자.

 

우선순위 큐의 시간복잡도는 O(log(N))

최악의 경우 모든 데이터를 한 번씩 삽입했다가 삭제한다고 하더라도 로그값이기 때문에 매우 작은 값이 나온다.2*log(2,250,000) = 약 12,,메모리도 최대 1500개 까지만 큐에 저장되기 때문에 충분할 것이다.

 

소스코드

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 우선순위 큐의 사이즈가 N개가 될 때까지 채우고, N개가 넘으면 pop하고 넣는다.

		int n = Integer.parseInt(br.readLine());
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

		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());
				// n*n 크기의 입력이 주어지기 때문에 i<1로해도 pq.size()>n 완전히 조건과 똑같다.
				if (i < 1) {
					pq.add(num);
				} else {
					if (pq.peek() < num) {
						pq.poll();
						pq.add(num);
					}
				}
			}
		}
		System.out.println(pq.peek());
	}

}