알고리즘 스터디 #3

정렬 - H_index
https://programmers.co.kr/learn/courses/30/lessons/42747

1. citations 배열에서 제일 많이 인용된 횟수가 n 일때 길이가 n+1인 used_arr 배열을 생성한다.

( 배열시작을 0이 아닌 1부터 사용하기 위해서 )

python

used_arr = [0 for i in range(max(citations)+1)]

java

int biggest = 0;
for(int i=0;i<citations.length;i++) {
  biggest = Math.max(biggest,citations[i]);
}
int [] used_arr = new int [biggest+1];

2. citations 배열로 반복문을 돌려 인용된 횟수에 해당되는 배열에 1을 더한다.

(n번 인용된 논문이 몇개인지 알 수 있다)

python

for i in citations : used_arr[i] += 1

java

for(int work:citations) used_arr[work]++;

3. used_arr 배열 뒤부터 반복문을 돌린다.

(더많이 인용된 논문들이 인덱스보다 크거나 같으면 인덱스를 H_index에 저장하고 break)

python

sum = 0
for i in range(len(used_arr)-1,-1,-1):
  sum += used_arr[i]
  if sum >= i : return i

java

int sum = 0, H_index = 0;
for (int i = biggest ;i >= 0;i--){
  sum += used_arr[i];
  if( i <= sum ){ H_index = i; break; }
}
return H_index;

최종코드

Python3

def solution(citations):
    answer = 0
    used_arr = [0 for i in range(max(citations)+1)]
    for i in citations : used_arr[i] += 1
    sum = 0
    for i in range(len(used_arr)-1,-1,-1):
        sum += used_arr[i]
        if sum >= i:return i

Java

import java.util.Arrays;
class Solution {
    public int solution(int[] citations) {
        int biggest = 0;
        for(int i=0;i<citations.length;i++) biggest = Math.max(biggest,citations[i]);
        int [] used_arr = new int [biggest+1];
        for(int work:citations) used_arr[work]++;
        int sum = 0, H_index = 0;
        for (int i = biggest ;i >= 0;i--){
            sum += used_arr[i];
            if( i <= sum ){ H_index = i; break; }
        }
        return H_index;
    }
}