반응형
2075번: N번째 큰 수
첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.
www.acmicpc.net

풀이
N*N 크기의 2차원 배열에서 N번째 큰 수를 찾으면 된다.
우선순위 큐를 사용하면 쉽게 해결할 수 있다.
기본적으로 오름차순으로 정렬되기 때문에 N번째 큰 수를 찾기 위해서는 정렬을 재정의해주어야 한다.
단순 integer형 큐이기 때문에 Collections.reverseOrder() 를 사용해서 역순으로 정렬해 주었다.
이후에 N-1번째까지 pq.poll()을 해주고, pq.poll()을 한 번 더 사용해서 출력했다.
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)); StringTokenizer st; int N = Integer.parseInt(br.readLine()); PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder()); for (int i=0; i<N; i++) { st = new StringTokenizer(br.readLine()); for (int j=0; j<N; j++) { pq.add(Integer.parseInt(st.nextToken())); } } for (int i=0; i<N-1; i++) { pq.poll(); } System.out.println(pq.poll()); } }
반응형
'알고리즘 > 정렬' 카테고리의 다른 글
[백준]JAVA - 10800번: 컬러볼 (0) | 2023.01.30 |
---|---|
[백준]JAVA - 10814번: 나이순 정렬 (0) | 2022.11.05 |
[백준]JAVA - 1181번: 단어 정렬 (0) | 2022.10.09 |
[백준]JAVA - 10815번: 숫자 카드 (0) | 2022.09.15 |