[프로그래머스] H-Index - Java

문제

---

https://school.programmers.co.kr/learn/courses/30/lessons/42747

프로그래머스

• 소요 시간 : 1
• 난이도 : LV 2

나의 풀이

---

 

접근 방법

1. 정렬한다.

2. 뒤에서부터 찾으면서 인용 수가 카운트보다 적거나 같은 지점을 찾는다. 

// 0, 1, 3, 5, 6
6번 이상 6 > 1개
5번 이상 5 > 2개
3편 이상 3 = 3개

시간복잡도

O(N)

N = citations의 길이

코드

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        
        Arrays.sort(citations);
        
        for(int i=citations.length-1; i>=0; i--) {

            // h번 이상 인용된 논문 
            int h = citations[i];
            answer = h;

            int count = citations.length - i + 1;
            if (h <= count) {
                break;
            }
            
        }
        
        return answer;
    }
}

 

결과 : 실패

---

다른 사람의 풀이

---

접근 방법

원소 값은 점점 감소하고, 원소 값 이상인 것의 개수는 점점 감소하므로

이 두 값의 최소값의 변화가 증가하다가 감소하는 지점을 찾으면 답이 된다.

시간복잡도

O(N)

N = citations의 길이

코드

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);

        int max = 0;
        for(int i = citations.length-1; i > -1; i--){
            int min = (int)Math.min(citations[i], citations.length - i);
            if(max < min) max = min;
        }

        return max;
    }
}

 

결과 : 정답

 

정리

---

와우..