백준 22282번 H-Index JAVA

링크텍스트

설명

프로그래머스 Lv. 2 H-Index와 같은 문제이다. 링크텍스트
다른 점이 있다면 n의 범위가 1~100000으로 프로그래머스보다 훨씬 넓기떄문에 기존에 내 코드로는 시간초과가 난다. 그래서 코드를 수정했다.
시간복잡도: O(N), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int [] arr = new int[n];

        for(int i=0;i<arr.length;i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        Arrays.sort(arr);

        int max = 0;
        // for(int i=1;i<=n;i++){
        //     int count = 0;
        //     for(int j=0;j<n;j++){
        //         if(arr[j]>=i){
        //             count++;
        //         }
        //     }
        //     if(count>=i) max++;
        // }

        for(int i=0;i<n;i++){
            int smaller = Math.min(arr[i],n-i);
            max = Math.max(max,smaller);
        }

        System.out.println(max);
    }
}