Hindex - 프로그래머스 [자바]
링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42747
문제
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
- 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
입출력 예
[3,0,6,1,5] return 3
접근 방식 : 국어 문제
문제를 잘읽고 구현한다.
다른 여럿 풀이들을 보았지만, 문제의 조건을 읽지 않고 자의적으로 해석한 풀이가 많다.
이문제는 문제를 잘읽고 코딩으로 구현하는 기초적일 수 있는 문제이다.
거창하게 Hindex 가 무엇인지 찾을 생각도 안하는게 좋다. 시험장에서 지식이 부족하다고 검색할 수 없지 않은가?
말이 이상한 경우 기초로 돌아가서 생각하자.
우선 기본이다 .
컴퓨터의 기본 조건문을 배울때 우리는 And 와 OR 를 배운다 .
And : 그리고
OR : 또는
매우 쉽다.. 이제 문제를 읽어 보자
H-Index는 다음과 같이 구합니다.
어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고
나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
이제 내가 빠진 함정이다.
[1,1,2,3,4] 가 input 으로 주어지면 , index =0 , 즉 1 인경우 나머지 논문이 어떻게 되지 ??
h = 1 이라면 , 5편의 논문중 1 번 이상 인용된 논문이 5편 이상이고 나머지 논문이,, 없다 ?
많은 블로그들이 이의 대한 답변을 하지않거나 , 숨기는 것들을 볼 수 가 있었다.
이에 대한 내 생각은
1. 문제의 조건에서 hindex 가 없는 경우의 대한 설명이 없으니 무조건 hindex 가 있다.
2. 나머지 논문의 대한 조건을 만족하는 방식으로 코드를 짜야한다. 무시하는게 아니라 .
예시를 하나 더 생각했다.
input : [1000]
위의 경우 hindex 는 1 인 것 같지만 나머지 논문이 없으니 구할 수 없다.
그러나 주어진 입력값을 정답으로 가지는 것 이 아닌 배열의 길이로 접근을 해야하는것을 안다.
예시를 하나 더 생각했다.
input : [2,4,4,4]
위의 경우 hindex 는 3 이다. 3 번 이상 인용된 논문 수 3개 나머지 논문 1 편이 3번 이하로 인용됨
위의 경우 hindex 는 4 가 불가하다. 4번 이상 인용된 논문 수 3개 hindex 불가능 .
정리를 하면
1. 배열의 길이를 고려하는 생각을 해야 하고
- 정답이 주어진 원소가 아닌 경우가 있다.
2. h 를 기점으로 인용된 논문 수를 새야한다.
3. [2,4,4,4] 과 같은 입력을 처리하기 위해서 2 부터 확인하면 나머지 논문이 없으므로 뒤에서 부터 처리한다.
문제 조건을 다시본다.
n편 중, h번 이상 인용된 논문이 h편 이상이고
나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.
ex ) A이고 B이다 . A and B
-> 주어진 조건은 AND 로 처리하라고 알려준다. hindex 의 후보를 고른 후 인용 이상, 이하 조건문을 만든다.
제한 사항을 다시본다
제한사항
- 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
- 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.
-> O(N^2) 이 가능한 풀이이다. :
논문별 인용 횟수의 최대값 10,000 에서 , 1,000편 이하의 논문 수를 확인하며 1씩 감소하면서 내려와도 괜찮다는 크기로 주어졌다.
class Solution {
public int solution(int[] cit) {
int answer = 0;
Arrays.sort(cit);
int hIndex = 0 ;
int n = cit.length ;
for(int i = cit[n-1];i>-1;i--) { // 주어진 입력값의 최댓값을 기준으로 -1 씩 탐색
int h = i; // h 후보
int countUP = 0 ; // 조건문 h 이상 확인
int countDown = 0 ; // 조건문 h 이하 확인
for(int j = 0 ; j< n;j++) {
int checKH = cit[j];
if ( h <= checKH ) {
countUP = n-j;
countDown = j;
break;
}
}
if(countUP >= h && countDown <= h) {
return h; // Hindex 의 최댓값이므로 바로 리턴 해도된다.
}
}
return -10000000; // 문제 조건의 맞지 않은 입력은 안준다라는 의지
}
}결과
