백준 2075 - 자료구조

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

//1. Collections.sort(list) 사용
public class Main{
	
 	public static void main(String[] args) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		StringTokenizer st = new StringTokenizer(br.readLine());
 		int N = Integer.parseInt(st.nextToken());
 		List<Integer> list = new ArrayList<>();
 		for(int i = 0; i < N; i++) {
 			st = new StringTokenizer(br.readLine());
 			for(int j = 0; j < N; j++) {
 				list.add(Integer.parseInt(st.nextToken()));
 			}
 		}
 		Collections.sort(list);
 		System.out.println(list.get(N*N - N));
 	}
}

// 2. PriorityQueue 사용 (최소 힙)
public class Main{
	
 	public static void main(String[] args) throws IOException {
 		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 		
 		PriorityQueue<Integer> pq = new PriorityQueue<>();
 		int N = Integer.parseInt(br.readLine());
 		
 		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());
 				pq.offer(num);
 				if(pq.size() > N) pq.poll();
 			}
 		}
 		System.out.println(pq.poll());
 	}
}

풀이과정 및 리뷰

1. Collections.sort(list) 사용

• 데이터 수가 적어서 그런지 시간초과 안뜨고 잘 제출되긴 했지만, 너무 효율적이지 않아서 다른 방법 추가
• 리스트 크기: N^2
• 정렬 시간복잡도 : O(N^2 log N^2) ≈ O(N^2 log N)
• 전체 시간복잡도 : O(N^2 log N)

1. PriorityQueue 사용

• 우선순위 큐를 사용해, 가장 큰 순으로 N번째 원소를 찾아야 하므로 pq.size() > 5 가 되면 제일 최상단(가장 작은 수가 최상단에 위치) 값을 꺼내도록 pq.poll() 해줌
• 전체 시간복잡도: O(N^2 log N)

(추가) 둘 다의 시간복잡도는 같게 나오지만,

• ArrayList 방식은 2,250,000개의 수를 정렬해야 하므로, 시간과 메모리 둘 다 크게 소모됨.
• PriorityQueue 방식은 항상 N = 1,500개만 저장하기 때문에 훨씬 효율적.