[정렬] 가장 큰 수, H-Index

가장 큰 수는 사실 이전에 순열을 이용하여 풀어보려고 시도했다가 포기했던 문제였다.

순열로 푸니까 런타임 에러가 자꾸 나는데 다른 사람들의 질문을 보니까 나만의 문제는 아닌 것 같다.

애초에 이 문제는 순열이 아니라 정렬로 접근하게 만들어져있는데 순열과 경우의 수를 공부한 것은 나중에 정리해서 포스팅하도록 하고 일단 정렬부터 먼저 정리해본다.

자바스크립트에서 사실 정렬은 꽤 쉬운 편이다. sort 함수가 있기 때문에 정렬 순서를 정의하는 compare function만 잘 만들어주면 되기 때문이다. 

가장 큰 수 

문제: 주어진 정수 배열을 문자열 붙이듯 이어붙여서 가장 큰 수 만들기

문제해결 방법은 크게 두 부분으로 나뉜다.

첫 번째는 정수 배열을 이어붙이기

두 번째는 가장 큰 수 뽑기

이전에는 정수 배열을 붙이는 방법을 순열로 접근했는데 "다른 사람 풀이"를 보고 난 뒤에

sort로도 충분히 할 수 있고 동시에 큰 수 뽑기 또한 할 수 있다는 것을 알게 되었다.

 

처음 접근 방법은 정수 배열을 모두 1의 자리수로 만들어서 큰 것부터 붙이는 방법이었는데 

구현 해보니까 10 이상의 수를 1의 자리로 만든 배열을 또 기존 배열에 넣거나 새로운 배열을 만들어서 모두 복사해서 이동해야하는데 생각보다 비효율적이라 구현하다가 그만두었다.

 

두 번째는 "다른 사람의 풀이"처럼 붙이기 전에 다른 경우의 수와 비교해서 큰 것들을 붙이는 방법이다.

예를 들어 6, 10이 있을 때 610과 106을 비교하여 순서를 바꿔준다. 아 물론 합치는 것은 이 모든 과정이 끝난 이후이다.

function solution(numbers) {
    let answer = numbers.map(v=>v+'')
    .sort((a,b)=> (b+a)*1 - (a+b)*1)
    .join('')
    
    return answer[0] === '0' ? '0' : answer
}

H-Index

조건: 논문의 인용횟수를 나타내는 (논문 수만큼의 길이를 가진) 배열

문제: n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 과학자의 h-index

 

처음에는 배열에 있는 인용횟수만 답이라고 생각해서 잘못 풀었다.

예를 들어

[0, 1, 3, 5, 6]이 있을 때 3이 답이 되는데 이를 3의 인덱스 2와 논문수 5를 활용하여 n - index >= value로 생각했다

하지만 [0. 1, 3, 5, 6, 7, 8]이 있을 때는 4편 이상 인용된 논문이 4개 이상이기 때문에 답이 4가 된다. 

따라서 n - index >= value로 풀 수 없다.

이런 경우 최소로 n - index < value일 때 n - index가 기존 h보다 큰 지 확인 한 후 h 값을 갱신한다.

function solution(citations) {
    
    var array = citations.sort((a,b) => a - b)
    var len = array.length
   
    var h = 0;
    for (let i = 0; i < len; i++){
        if(len - i >= array[i]){
            h = array[i]
        }
        if(len - i > h && len - i < array[i]){
            h = len - i
        }
    }
    return h;
}

일단 맞았긴 한데 정석적인 방법이 아니라 다른 사람의 코드를 확인해보았다.

 

역시 그냥 h값을 0부터 차례대로 늘려가는 방법들이 대부분이었다.

그리고 이때에는 내림차순으로 정렬하여 i값이 인용횟수를 넘어갈 때 while문을 탈출하게 되어있다. 

예를 들어 [0. 1, 3, 5, 6, 7, 8]이 있으면

[8, 7, 6, 5, 3, 1, 0]으로 정렬하고

1->2->3->4로 늘리다가 탈출한다.

내 방법보다 훨씬 더 깔끔한 방법이다.

function solution(citations) {
     citations = citations.sort((a, b) => b - a);
     var i = 0;
     while(i + 1 <= citations[i]){
         i++;
     }
     return i;
}