프로그래머스 - H-Index

카테고리: 정렬

레벨: 2

언어: Java

 

문제

---

처음에 문제를 읽었을 때 뭔가 쉬워 보이면서도 이해가 안 가는 문제였다. 그래도 친절하게 위키백과에서 H-Index에 관한 개념을 확인할 수 있어서 읽어보니 바로 이해할 수 있었다.

h-index - Wikipedia

 

밑의 예시로 설명을 잠깐 해보면 배일의 크기는 5이므로 총 5편의 논문을 발표했고, 배열의 각 값들은 논문 마다 인용 횟수를 보여준다.

밑의 입출력 예시를 통해서 [3, 0, 6, 1, 5] 배열이 주어진다면 3번 이상 인용된 논문은 3편이지만, 4번 이상 인용된 논문은 4편이 되지 않는다.

여기서 우리가 알 수 있는 부분은 i번 이상 인용된 눈문의 개수 j가 같아야 된다는 것을 알 수 있다.

 

입출력 예시

---

 

풀이

---

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

    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < citations.length; i++) {
        list.add(citations[i]);
    }

    list.sort(Collections.reverseOrder());

    for (int i = 0; i < list.size(); i++) {
        if (list.get(0) == 0) {
            return 0;
        } else if (list.get(i) <= i) {
            break;
        } else {
            answer++;
        }
    }
    return answer;
}

풀이를 살펴보면 먼저 매개변수로 받은 citations 배열을 ArrayList에 담아서 Collections.reverseOrder()를 통해 내림차순 정렬을 해준다.

그 다음으로 list의 i번째 값과 현재 i의 값이 같다면 break를 통해서 반복문을 종료해 주고, 같지 않다면 answer 값을 증가시켜 준다.

마지막으로 answer 값을 반환해주면 끝이 난다.

말로 설명하니 이게 무슨 소린가 싶어서 그림을 통해 이해를 해보자.

 

Collections.reverseOrder()를 사용하면 그림과 같이 내림 차순으로 정렬이 가능하다.

정렬이 완료되고 나면 반복문을 통해서 값을 하나씩 비교해 주면 된다.

 

만약 i값이 list의 i번째 값과 비교하여 더 크다면 i번 만큼 인용되지 못했다고 판단하고 break를 통해서 반복문을 종료하게 된다.

반대로 i값이 list의 i번째 값과 비교하여 작다면 answer를 증가시켜 준다.

여기서 우리가 생각해 봐야 될 2가지 예외가 있다.

 

첫 번째로는 배열의 값으로 전부 0이 들어왔을 때이다.

if (list.get(0) == 0) {
    return 0;
}

list에서 0번째 인덱스 값을 가져왔는데 만약 0이라면 내림 차순 정렬한 배열에서 제일 높은 값이 0이라는 뜻이므로 인용이 되지 않았다는 뜻으로 0을 반환해 준다.

 

두 번째 예외 상황으로는 i와 list의 i번째 값이 같을 경우다.

else if (list.get(i) <= i) {
    break;
}

이러한 경우는 그냥 <=을 추가하여 같은 경우에도 break 할 수 있도록 설정해 주면 된다.