백준 2075번 : N번째 큰 수 (JAVA)

문제

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번째 큰 수를 출력한다.

 

---

 

풀이

풀이 1

최소 힙을 만들고, N^2개의 숫자를 도는 동안 힙의 원소를 N개가 되도록 한다. 이후 힙에서 바로 빼버리면 그 숫자는 N번째로 큰 값이 된다.

시간 복잡도 O(N^2logN), 공간 복잡도 O(N)를 갖는다. 메모리 제한이 이 풀이를 강제하기 위해 존재한다고 생각했는데, 게시판(https://www.acmicpc.net/board/view/36675)을 살펴보니 딱히 그렇지는 않다고 한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
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));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		
		PriorityQueue<Integer> pq = new PriorityQueue<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				pq.offer(Integer.parseInt(st.nextToken()));
				if (pq.size() > N) pq.poll();
			}
		}
		
		System.out.println(pq.poll());
	}

}

 

풀이 2: 우선순위 큐에 N^2개의 원소 다 넣어버리기

최대 힙을 선언하고, 말 그대로 다 넣고 본다.

이후 빼내는 작업 N번 반복, N번째로 나오는 숫자가 N번째로 큰 수

시간 복잡도 O(N^2logN), 공간 복잡도 O(N^2)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
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));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		
		PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				pq.offer(Integer.parseInt(st.nextToken()));
			}
		}
		
		for (int j = 0; j < N-1; j++) {
			pq.poll();
		}
		
		System.out.println(pq.poll());
	}

}

 

풀이 3: 내 풀이

N^2를 배열에 저장한 후, 문제 조건대로 맨 마지막 행의 N개 값을 index정보를 포함하여 우선순위 큐에 저장한다.

빼내면서 받은 값의 row, col, value값에 대하여 row-1, col과 matrix[row-1][col] 값을 우선순위 큐에 넣어준다.

시간 복잡도 O(N^2), 공간 복잡도 O(N^2)

 

코드

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));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int[][] matrix = new int[N][N];
		int[] indexArray = new int[N];
		for (int i = 0; i < N; i++) indexArray[i] = N-1;
		
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> {
			return -Integer.compare(o1[2], o2[2]);
		});
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int j = 0; j < N; j++) {
			pq.offer(new int[] {N-1, j, matrix[N-1][j]});
		}
		
		for (int i = 0; i < N-1; i++) {
			int[] temp = pq.poll();
			int row = temp[0];
			int col = temp[1];
			pq.offer(new int[] {row-1, col, matrix[row-1][col]});
		}
		
		System.out.println(pq.poll()[2]);
	}

}

 

결과

위에서부터 차례대로 풀이 1, 풀이 2, 풀이 3.

 

의문점 (진짜 모름)

1. 풀이 3이 상수배 연산이 좀 자잘하게 시간이 오래 걸리긴 할 거 같은데, N = 10^3 정도의 사이즈에서는 log(N^2)가 대략 20 정도 나오니 풀이 2, 3보다 유의미하게 빠를 듯한데, 왜 소요 시간은 거기서 거기일까?
2. JAVA는 기본적으로 메모리를 많이 쓰는 듯한데, 왜 그럴까?