[백준 JAVA] 2075번: N번째 큰 수

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

 

처음에 가장 쉽게 풀 수 있는 방법을 떠올려 봤을 때 우선순위 큐에 모든 수를 넣고 N번 뺀 결과를 넣는것이었다.

 

우선 수의 갯수는 N <= 1500 이므로 N^2 = 2250000 = 약 200만개이고 수를 뺄때 또 N번 계산해야 하므로 N^3 = 30억 정도여서 모든 계산이 1초안에 끝난다 해도 좀 힘들꺼같았다.

 

그래서 문제에 있는 조건인 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것을 이용해야 할 꺼 같았는데

 

우선 처음으로 가장 큰 수를 찾을때 맨 아래줄에서만 찾으면 된다.

 

그리고 그다음 큰 수를 찾을때는 이전에 찾았던 수는 바로 위에 칸에서 찾고 나머지는 다시 맨 아래줄에서 찾으면 된다.

 

따라서 해당 열을 몇번 방문했느냐를 int 배열로 관리해서 매번 N 개 만큼 찾으면 N * N 만에 찾을 수 있을꺼같아서 해당 방법으로 문제를 풀어보앗다.

 

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

public class Main {
    static int N;
    static int[][] map;
    static int[] visited;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new int[N];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int idx = 0;
        int max = 0;
        for(int i = 0; i < N; i++){
            max = Integer.MIN_VALUE;
            for(int j = 0; j < N; j++){
                int k = N - visited[j] - 1;
                int v = map[k][j];
                if(v > max){
                    idx = j;
                    max = v;
                }
            }
            visited[idx]++;
        }
        System.out.println(max);
    }
}

 

풀긴 풀었는데 GPT 피드백을 들어보니 그냥 우선 순위 큐를 사용해도 되는 문제였다고 한다.

 

이유를 설명하자면 나는 우선순위큐를 사용하는 방식의 시간복잡도가 O(N^3) 라고 생각했지만 사실 N^2(log(N^2))에서 N log(N^2)을 곱하는게 아니라 더하는것이므로 N log(N^2)이 무시될만큼 작아서 실제로 O(N^2 * log(N^2)) 만큼 걸린다.

 

그래서 우선순위 큐 방법으로도 풀었지만 이론적으로 O(N^2)인 내 방법이 좀 더 시간이 적게 걸리는것을 확인할 수 있었다.