프로그래머스 - H-Index

프로그래머스 - H-Index

import java.util.Arrays;

class Solution {
	public int solution(int[] citations) {
		// n편 중 h번 이상 인용된 논문이 h편 이상, 나머지 논문이 h번 이하 인용 -> h의 최대값
		// 1, 정렬 하고 최대 인용된 수를 구함
		// 2. 기준이 1일때 1이상인 인용 수 / 이하인 인용수 , 1이상 ~ 최대H까지 반복
		// 2-1. 논문수 - 인용수
		// 3. 탐색하면서 인용 수가 이하 인용수 이상일때까지 인덱스 증가, 멈추면 해당 숫자가 인덱스

		// 정렬
		Arrays.sort(citations);

		// 최대 인용된 수
		int n = citations[citations.length-1];

		int nonMoonCount = citations.length;

		// 인용횟수 이상 저장 배열
		int[] resultArr = new int[n+1];
		int[] cantResultArr = new int[n+1];

		for(int i=1; i< resultArr.length; i++) {
			int count = 0;
			for(int j=0; j<citations.length; j++) {
				// 인용 횟수를 각각 탐색하며 i번째 이상 인용 했다면 횟수 증가
				if(citations[j] >=i) {
					count++;
				}
			}
			// i번 이상 인용된 논문 수
			resultArr[i] = count;
			// 전체 논문 수 - i번 이상 인용된 논문 수 : i번 이하 인용수
			cantResultArr[i] = nonMoonCount - count;
		}

		int hIndex = 0;

		for(int i=1; i< resultArr.length; i++) {
			// H-Idex : h번 이상 인용된 논문이 h번 이상 & 나머지 논문이 h번 이하라면 갱신
			// 최대 돌때까지 
			if(resultArr[i] >= i && cantResultArr[i] <= i) {
				hIndex = i;
			}
			// 위 조건이 맞지 않기 시작하면 이후부터는 다 아니니 종료
			else {
				break;
			}
		}
		return hIndex;
	}
}

• 인용수를 정렬하고, 최대 인용수(n)를 구한다.

• 1번 ~ 최대 인용수를 반복하며, 1번 인용된 수 / 인용 안된수 를 각각 resultArr과 cantResultArr의 인덱스에 횟수를 집어넣는다.

• 이렇게 하고 탐색을 하면서, 1번 인용되었을 때 h-index 조건을 만족하는가? 만족하면 그 1로 갱신, ... 최대 인용된 n 까지 탐색을 해본다.

• 탐색을 하다 보면, 나머지 논문이 h번 보다 커지는 숫자 에서는 h-index 조건을 만족하지 않으니깐 반복문을 종료시켜준다. (최대 h-index를 구한 상태, 그 다음 숫자)

• 문제에서 주어진 예시를 적용시키면

resultArr(index)	value	cantResultArr(index)	value
0	0	0	5
1	4	1	1
2	3	2	2
3	3	3	2
4	2	4	3
5	2	5	3
6	1	6	4

• resultArr의 인덱스번 이상 인용된 논문 수 : count개
• cantResultArr의 인덱스번 이상 인용되지 않은 논문 수 : nonmoonCount - count
  • 즉 전체 논문 개수 5개 - 인용 논문 수
• 인용 수 자체로 배열을 구성한 것으로, 3번 인덱스 까지가 가장 마지막 조건을 만족하고 4번으로 넘어갈 경우 break로 반복문을 탈출하게 된다.
  • 조건 : h(i)번 이상 참조된 논문 수, h(i)번 이하 참조되지 않는 논문 수 최대 h(i)값