[프로그래머스] h-index (정렬)

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

코딩테스트 연습 - H-Index

2021-07-26

---

1. 절반을 나눠서 해야한다고 생각했을 때 (너무 복잡하다)

import java.util.Arrays;
 
class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        int index = citations.length % 2 == 0 ? citations.length/2-1 : citations.length/2;
        int h = citations.length - index;
 
        boolean flag = false;
        while(true) {
            if(index >= citations.length) break;
            if(citations[index] >= h) {
                if(index == 0) break;
                else index--;
                h++;
                flag = true;
            } else {
                if(flag) {
                    h--;
                    break;
                } else {
                    index++;
                    h = citations.length - index;
                }
            }
        }
        return h;
    }
}

 

 

#문제풀이

0. 오름차순 정렬

 

1. 일단 기준점(index)를 배열 길이의 중앙으로 잡았다. 

 

2. 그리고 citations 에서 index만큼 뺀 값을 (임시) h값으로 두었다.

 

3. index값을 길이의 중앙으로 했더니 너무 복잡해졌다. index를 ++만 할 수도 --만 할 수도 없는 상황이어서, 두 가지 경우의 수를 나눠줘야했다. 일단, 이를 위해서 boolean flag를 두었고, 

 

4. 만약 현재 index의 citations값이 h(citations.length - index)값보다 크거나 같으면, h값의 후보가 될 수 있다. 하지만, 최대값을 구하는 것이므로, 다른 값을 찾기 위해 계속 움직여야한다. 그래서 이렇게 값을 하나 찾았으면 일단 flag = true로 바꿔놓았고, 기준 h값을 ++ 올렸다. 

 

5. 만약 현재 index의 citations값이 h 값보다 작다면, h값으로 사용할 수가 없다. 이 때 index를 중앙으로 해놓은 것 때문에 또 문제가 생긴다. (1) 값을 이미 찾았는데 최댓값을 찾다가, h값보다 작은 경우를 만난 경우 (2) 값을 한 번도 찾지 못했는데, h값보다 작은 경우이다. 

 

두 가지 경우를 나눠서 생각했고, (1) 번 (flag == true)의 경우에는 h--를 해주면 마지막으로 찾은 h의 값이므로 함수를 끝낸다.

(2)번 (flag == false)의 경우에는 index++를 해주어서, (임시)h값을 바꿔주어, 또 다른 값을 찾을 수 있게 만들어주고 반복한다.

 

이렇게 했을 때, 문제점이 많았다. 일단 생각해야하는 케이스가 많았고 코드도 아래 2번에 비해서 2배 정도가 되버렸다. 

그래서, index 기준점을 다시 잡고 풀어보았다. 

 

2. 굳이 절반을 나눠서 할 필요가 없다고 생각했을 때

import java.util.Arrays;
 
class Solution {
    public int solution(int[] citations) {
        Arrays.sort(citations);
        int index = 0;
        for(index = citations.length - 1; index >= 0; index--) {
            if(citations[index] < citations.length - index) break;
        }
        return citations.length - index - 1;
    }
}

#문제풀이

index 기준점을 배열의 길이 -1, 즉 맨 끝에 배열로 잡으니깐 훨씬 수월하게 풀 수 있었다.

 

0. 오름차순 정렬

 

1. index는 citations.length - 1부터 시작하고, citations[index] 값을 1부터 차례대로 (citations.length - 1) 하나씩 비교 해줬다. 

 

2. 이 때, citations[index] 값이 citations.length - index 값보다 작으면 즉, h값이라고 부를 수 없는 값이라면 함수를 끝내줬다. 

 

3. 그렇게 나온 index값이 우리가 찾는 h점의 기준점이 되고, citations.length - index를 해주면 h-index를 찾을 수 있다. 단, for문을 끝내면서 index--를 한 번 더 안 해줘서, 마지막에 return 할 때 -1을 해주었다. 

 

 

+) 그 외 풀면서 찾은 반례/테스트케이스

{1, 2, 5, 9, 10}  =>  3

{0, 0, 0}  =>  0

{0, 0, 1, 0, 0}  =>  1

{3, 4, 5, 8, 10}  =>  4

{11, 22}  =>  2