[프로그래머스] h-index (정렬)
https://programmers.co.kr/learn/courses/30/lessons/42747
코딩테스트 연습 - H-Index
H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표
programmers.co.kr
2021-07-26
1. 절반을 나눠서 해야한다고 생각했을 때 (너무 복잡하다)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
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;
}
}
|
cs |
#문제풀이
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. 굳이 절반을 나눠서 할 필요가 없다고 생각했을 때
|
1
2
3
4
5
6
7
8
9
10
11
12
|
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;
}
}
|
cs |
#문제풀이
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