Today's Algorithm(2019-01-09)

programmers. H-Index

이 문제는 문제풀이 자체는 문제 자체를 이해하는데 힘들었던 문제였습니다. 그 놈의 h가 뭔지.. h번 이상 인용된 논문의 수가 h이고, 나머지 논문들이 h이하 인용이 되었다면 그 h를 구하라는 문제인데요. h h h h h 정말 헷갈렸습니다. 어느 순간 제가 h를 구하고 있는건지, 무엇을 구하고 있는건지 길을 잃기도 했습니다. 말로 설명하기 힘드니 코드로 살펴볼게요

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        List<Integer> list = new ArrayList();
        for (int citation : citations) {
            list.add(citation);
        }
        Collections.sort(list);

        int last = list.get(list.size() - 1);
        for (int h = 0; h <= last; h++) {
            int above = 0;
            for (Integer i : list) {
                if(i >= h) above++;  // h번 이상 인용 논문 개수
            }
            int below = list.size() - above;  // 나머지 논문 개수

            if(above >= h && below <= h) {
                answer = h;
            }
        }

        return answer;
    }
}

이전에 답을 제출할때 테스트케이스 중 하나가 통과가 안됐는데요. 그 이유는 제가 for문 내 조건이 만족되면 break해버렸기 때문입니다. 그런데 h가 가장 큰 수가 나오게 하는게 문제의 의도이다보니 조건을 만족하는 h를 모두 탐색하여야 했습니다. 그렇기 때문에 break대신 answer를 갱신하는 구조로 수정하였습니다. 

코드로 살펴보니 제가 이전에 왜 삽질을 했는지 이해가 안가도록 쉬운 코드였네요.. 다만 저는 복잡도가 O(n^2)인데요. 그 부분에선 아쉬움이 남습니다. 다른 사람의 답변을 보니 O(n)으로 푸신 분들도 있더라구요. 내일은 그분들 코드를 이해하기 위해 한번 노력해보려 합니다.