코딩테스트 준비 - H - Index

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : Programmers

• 문제 : H - Index

• 사용언어 : C#

• 난이도 : 중상

• 풀이시간 : 1h 49m

• 유형 : 정렬, 문제이해, 인덱스

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.

• 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

입출력 예

citations return [3, 0, 6, 1, 5] 3

입출력 예 설명

이 과학자가 발표한 논문의 수는 5편이고, 그중 3편의 논문은 3회 이상 인용되었습니다. 그리고 나머지 2편의 논문은 3회 이하 인용되었기 때문에 이 과학자의 H-Index는 3입니다.

** H-Index 이해 필요 링크

문제 풀이 접근

이 문제는, 문제의 불친절함 때문에 여러번 낚였다.
구현과 생각을 4번 정도 변경해서 오래걸렸다.
여기서 말하는 H-Index의 비교수는 결코 Element의 값이 아니라 순수 Loop 되는 Index 로 생각하면 편하다.
문제를 다 풀고나서 생각이지만, 정말 이해하기 어려웠다.
위키피디아 보고나서 5분만에 고쳐서 해결했다.

이 문제의 플로우는,
1. 받은 배열을 정렬한다. (내림차순)
2. 진행한 인덱스 i 의 값을 만족하지 못하는 수가 발견되면 break 해도 좋고, i 의 값 이상 인용된 논문을 찾아서 answer에 넣어주면 쉽게 풀린다.

정답 작성 코드 (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Array.Sort(citations);
        List<int> list = new List<int>();
        
        if(citations.Length == 1)
            return citations[0];
        
        for(int i =0; i < citations.Length; ++i)
            list.Add(citations[i]);
        
        list.Sort((int a, int b)=>{return b.CompareTo(a);});
        
        for(int i = 0; i < list.Count; ++i)
        {
            int index = i+1;
            int count = list.FindAll(rhs=> rhs >= index).Count;
            
            if(index <= count)
                answer = index;
        }

        return answer;
    }
}

코드 결과

다시 생각해봐도 정말 시간 아까웠다.
더빨리 풀 수 있었는데..

다시 푸는 것으로 동일한 문제에 대한 포스팅이 있다.
링크