[Java] 프로그래머스 Lv.2 : H-Index

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

코딩테스트 연습 - H-Index

문제이해가 잘 되지않아서 테스트 케이스를 많이 추가해서 풀었었다..

# 테스트 케이스 공유

Parameters	Return
[3, 1, 0]	1
[3, 1, 1, 1, 4]	2
[0, 0, 0, 1]	1
[9, 9, 9, 12]	4
[1, 1, 5, 7, 6]	3
[0, 0, 0] (테스트 16번)	0

 

풀이

h를 발표한 논문 수(n)의 중간값(n/2)으로 초기화 시킨다.

논문 n편 중 h번 이상 인용된 논문이 h편 이상인 시점을 찾기 위해(이때, n이 h보다 커질 수 없음) 반복문을 돌린다.

• (ctn-h)번째 논문의 인용횟수가 h번 이상일 때,
  • cnt-h-1번째 논문의 인용횟수가 h번 이하면 h값을 return
  • cnt-h-1번째 논문의 인용횟수가 h번 이상이면 인용횟수(h)를 증가
• (ctn-h)번째 논문의 인용횟수가 h번보다 작다면 인용횟수를 감소

이때, 인용횟수 h가 0이라면 0을 return한다.

밑의 코드에서 answer은 인용횟수 h이다.

import java.util.*;
class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        int n = citations.length; // 발표한 논문 수
        // citations 정렬
        Arrays.sort(citations);
        
        // answer 중간값으로 초기화
        answer = n/2;
        // citations[cnt - answer] 가 answer 이상, 남은 논문이 answer번 이하인지
        // 이하면 answer--
        while(answer<n){
            if(citations[n-answer]>=answer){
                if(citations[n-answer-1]<=answer) break; // 원소값이 인용횟수 이하인 시점에서 return
                answer++;
            }
            else answer--;
            if(answer==0) break;
        }
        
        return answer;
    }
}

 

+ 다른사람풀이

원소값은 점점 감소하고, 원소 값 이상인 것의 개수는 점점 감소하므로 이 두 값의 최소값의 변화가 증가하다가 감소하는 지점이 답이라는 규칙으로 풀어냈다.

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;
    }
}