[JAVA] H-index

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

프로그래머스

 

문제 이해하기 너무 힘들었다.. 다른 코드도 참고 하면서 이해하려고 노력했다..

일단 정렬을 해야한다. 

Array.sort 대신 퀵정렬을 이용해서 풀었다..!

 

예시

citations [5, 4, 7, 1, 2]

정렬한 citations [1, 2, 4, 5, 7]

1(i)회 이상 인용된 논문이 5편(1,2,4,5,7)

2(i)회 이상 인용된 논문이 4편(2,4,5,7)

4(i)회 이상 인용된 논문이 3편(4,5,7)

5(i)회 이상 인용된 논문이 2편(5, 7)

6(i)회 이상 인용된 논문이 1편(7)

이렇게 citations[i]에서 i값을 증가시키고 논문의 수를 감소시키면서 비교했을 때, 인용횟수(i)가 논문의 수 이상이 되었을 때 H-Index가 된다...! => 여기서 H-Index는 3! 

 

퀵정렬을 이용한 풀이

class Solution {
    public int solution(int[] citations) {
        int answer = 0;

        ascQuick(citations, 0, citations.length-1);
        
        for(int i=0;i<citations.length;i++) {
            if(citations[i] >= citations.length-i) {
                answer = citations.length-i;
                break;
            }
        }
        
        return answer;
    }
    
    public static void swap(int a[], int idx1, int idx2) {
        int tmp = a[idx1];  
        a[idx1] = a[idx2]; 
        a[idx2] = tmp;
    }
    
    public static void ascQuick(int[] a, int start, int end) {
        int pl = start;
        int pr = end;
        int pivot = a[(start + end) / 2]; 

        do {
            while (a[pl] < pivot)
                pl++; 
            while (a[pr] > pivot)
                pr--; 
            if (pl <= pr)
                swap(a, pl++, pr--); 
        } while (pl <= pr);

        if(start<pr)
            ascQuick(a,start,pr);
        if(pl<end) 
            ascQuick(a,pl,end);

    }
}

 

• 내림차순으로는 안되고, 오름차순으로만 된다..!

 

2. Math.min( )과 max( )를 이용한 풀이, sort( )

import java.util.*;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Arrays.sort(citations);
        
        for(int i=0; i<citations.length; i++){
            int h = Math.min(citations[i], citations.length-i);
            if(h >= answer) answer = Math.max(answer, h);
            else break;
        }
        return answer;
    }
}

 

• 두 값 중 작은 쪽이 H-Index가 된다.
• 최댓값을 갱신해 나가다 h가 answer보다 작을 때, for문 그만돌리기 

---

• 퀵정렬알고리즘은 이제 알겠다.. 다만 재귀함수라서 재귀 못쓸 때는 못써서.. 조금 슬프지만, 그래도 제일 빠른 시간 복잡도를 가지고 있기 때문에...!
• 만약 int[ ] 배열을 내림차순 하고 싶다면 Integer[ ]로 바꿔서 Collections.reverseOrder() 사용해야 한다. 
  
  •         Integer[] copyCitations = new Integer[citations.length];
            for(int i=0;i<citations.length;i++) {
                copyCitations[i] = citations[i];
            }
            Arrays.sort(copyCitations, Collections.reverseOrder());