알고리즘/프로그래머스 Level2

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

류창 2021. 12. 17. 21:48
반응형

 

문제분석

 

꽤나 당황스러운 규칙을 가졋습니다.

 

문제를 보니 위키백과를 링크를 해줬으니 들어가서 참고 하라는것 같습니다.

 

물론 보지않고 푸시는 분이 있겟지만, 저는 참고했습니다.

 

위키백과에서 제공하는 공식

 

도대체 이게 무슨 공식인가.. 하면

 

일단, 이 수식을 사용하려면  배열을 내림차순 정렬을 해달라고 했습니다.

 

헌데..  문제에서 준 int[] 배열은 내림차순 정렬을 그상태론 못합니다.

 

내림차순 정렬을 하기위해선, Collections.reverseOrder()나 comparator를 사용해야하는데, 

 

이 메소드를 지원하는건 객체 상태로 Wrapper된 타입만 지원합니다.

 

-> int[] 를  Integer[]로 바꿔야하죠

 

따라서, 그냥 오름차순 정렬을 한뒤, 뒤에서부터 탐색을 하기로 했습니다.

 

괜히 내림차순 정렬한다고 타입을 변환하는 연산이 추가로 더 들어가니깐요.

 

 

위키백과에서 설명하는 저 공식을 설명하자면,

 

i번째 원소값 >= i가 Max()인 값을 찾아주세요~ 라는겁니다.

 

즉, 오름차순정렬을 해놨으니 뒤에서부터 탐색해서  i번째 원소값 >= size-i  가 만족하지 못할때까지 

돌리면 H-Index가 나오게됩니다.

문제풀이

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        int size=citations.length;
        
        for(int i=size-1;i>=0;i--){
          int h =citations[i];
          if(h>=size-i){
              answer = size-i;
             
          }
          else{
              break;
          }
        }
        return answer;
    }
}
cs

 

반응형