[BAEKJOON] 2575번 N 번째 큰 수

문제
: N×N의 표에 수 N2개 채워져 있다. 그 중  N번째 큰 수를 찾는 프로그램을 작성하라

 

■ 1. 문제  설명

N=5

 

(1) 문제 설명

N×N의 표에 모두 다른 수가 채워져 있다.
채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. 
이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하라.

 

 

(2) 입출력예시

1. 예제 입력

=> 첫째 줄에 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

 

1. 예제 출력

35

 

 

---

 

 

 

■ 2. 문제  풀이

Queue                                                                                                                             슬라이딩 윈도우  알고리즘 

 

 

우선순위 큐와 슬라이딩 윈도우 알고리즘 적용

1. 우선순위 큐 : 기본적으로 오름차순으로 데이터를 정렬

2. 슬라이딩 윈도우 알고리즘 :  일정한 길이의 범위를 이동하여 조건에 맞는 값을 찾는다.

 

 

(1) 우선순위 큐 선언

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

 

(2) 우선순위 큐에 숫자를 담는다. => 메모리 속도 효율을 위해 첫 줄을 미리 넣는다..

st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
    pq.offer(Integer.parseInt(st.nextToken());
}

 

 

(3) 큐에 들어있는 가장 작은 값과 비교하여 데이터를 교체한다.

큐의 사이즈가 n이 되면 맨 앞의 숫자(n개의 수 중 가장 작은 숫자)와 새로운 값을 비교한다.

1. 새로운 값이 더 클 경우 데이터를 바꿔준다.
2. 새로운 값이 작을 경우 그대로 유지한다.

※ 큐의 최대 사이즈는 N으로 계속해서 데이터를 삭제, 삽입 해주므로 모든 데이터 N^2을 저장하여 정렬하는 방식보다 공간복잡도의 효율을 높여줄 수 있다.

for(int i = 1; i < n; i++) {
        st = new StringTokenizer(br.readLine());
        for(int j = 0; j < n; j++) {

            int temp = Integer.parseInt(st.nextToken());
			// 새로 들어온 값과 큐에 들어있는 가장 작은 값(q.peek())을 비교하여
            // 새로 들어온 값이 더 클 경우 데이터를 교체한다.
            if(pq.peek() < temp) {
                pq.poll();
                pq.offer(temp);
            }
        }
}
// 우선순위큐의 사이즈를 N 만큼 유지하면서 삽입/삭제를 반복하면
// 마지막에 남는 peek() 값이 N 번째로 큰 수가 된다.
System.out.println(pq.poll());

 

 

 

 

★  전체 코드

public void solution () throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

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

    st = new StringTokenizer(br.readLine());
    for(int i=0; i<n; i++) {
        int temp = Integer.parseInt(st.nextToken());
        pq.offer(temp);
    }

    for(int i=1; i<n; i++) {
        st = new StringTokenizer(br.readLine());
        for(int j=0; j<n; j++) {
            int temp = Integer.parseInt(st.nextToken());

            if(pq.peek() < temp) {
                pq.poll();
                pq.offer(temp);
            }
        }
    }

    System.out.println(pq.poll());
}