b.2075 N번째 큰 수

 

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

 

 

 

📌 자바(Java)로 푸는 N번째 큰 수 문제 - 백준 2075 🧮

 

---

🔎 문제 개요

 

백준 2075번 - N번째 큰 수 문제입니다.

N x N 크기의 행렬이 주어졌을 때, 모든 수를 정렬했을 때 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

💡 예제 출력

35

➡ 모든 수 중 5번째로 큰 수(내림차순 정렬 기준)는 35

 

---

🛠 접근 방식

 

현재 코드는 모든 값을 배열에 넣고 정렬한 뒤 N*N - N번째 값을 출력합니다.

즉, 내림차순 정렬 시 N번째 큰 수는 오름차순 정렬 시 (N*N - N)번째 인덱스에 위치한다는 점을 이용한 풀이입니다.

 

하지만 시간 및 메모리 측면에서 우선순위 큐(최소 힙)을 사용하는 방식이 더 적합합니다.

 

---

🔹 현재 코드 해설 (정렬 방식)

int[] arr = new int[N*N];

for(int i = 0 ; i < N ; i++){
    StringTokenizer st = new StringTokenizer(br.readLine());
    for(int j = 0 ; j < N ; j++){
        arr[i*N+j] = Integer.parseInt(st.nextToken());
    }
}

Arrays.sort(arr);
System.out.println(arr[N*N-N]);

✔ 모든 수를 arr[]에 저장하고

✔ 정렬한 후 (N*N - N)번째 인덱스 출력 → N번째 큰 수

 

---

 

📦 대안: 우선순위 큐(PriorityQueue)를 활용한 효율적인 풀이

PriorityQueue<Integer> pq = new PriorityQueue<>();

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.add(num);
        if (pq.size() > N) {
            pq.poll();  // N개를 초과하면 가장 작은 수 제거
        }
    }
}
System.out.println(pq.peek());

✔ 우선순위 큐를 이용해 항상 큰 수 N개만 유지

✔ 최종적으로 N번째 큰 수는 pq.peek()

---

 

🏆 정리

 

✅ 핵심 포인트

 

✔ N x N 행렬의 모든 값을 정렬하여 N번째 큰 수를 찾는 문제

✔ 단순 정렬 방식도 가능하지만, 우선순위 큐 사용이 더 효율적

✔ 입력이 커질수록 메모리와 속도에서 큐 방식이 유리함

---

🎯 이 문제를 통해 배울 수 있는 점

 

✅ N번째 큰 값을 구할 때는 “최소 힙”을 유지하는 방식이 효과적

✅ 배열 정렬 대신 우선순위 큐를 떠올리는 습관 기르기

✅ 입력이 크고 시간 제한이 타이트할수록 정렬보다 큐 방식 고려

---

 

이 글이 도움이 되셨다면 좋아요와 공유 부탁드립니다! 😊