[프로그래머스] 정렬 _ 가장 큰 수 / H-Index

2021_09_12 알고리즘 스터디 문제 풀이

 

1. 가장 큰 수  --> URL 

코딩테스트 연습 - 가장 큰 수

 

문제

처음에는 문제를 확인하고 자릿수가 작고 그 중에서도 큰 값을 기준으로 솔팅하면 된다고 생각했었다.

하지만 그럴 경우 입출력 예 2에 해당하는 정답이 "9533430"로 나오게 된다. 자릿수가 적은 것이 크기보다 우선으로 정렬이 되기 때문인데 가만히 생각을 하다보니 로직에 오류가 있다는 것을 깨닫고 수도코드를 새로 작성했다.

수도코드

numbers를 sort 메소드로 정렬한다, a, b
    a, b의 자릿수가 같지 않다면
        ab 스트링의 값과 ba의 스트링값을 비교하여 더 큰값을 가질 수 있는 요소를 더 낮은 인덱스에 배치한다
    a, b의 자릿수가 같다면
        더 큰 값을 낮은 인덱스에 배치한다
join 메소드로 요소를 이어 붙인다

만약 결과의 인덱스0 값이 '0'이라면 '0'만을 리턴한다

 

풀이

function solution(numbers) {
    const result = numbers.sort((a, b) => {
        if(String(a).length !== String(b).length) {
            const aValue = parseInt(a + '' + b);
            const bValue = parseInt(b + '' + a);
            
            if (aValue > bValue) return -1;
            if (aValue < bValue) return 1
            
        } else { 
            if (a > b) return -1;
            if (a < b) return 1;
        
        }
    }).join("")
    
    if (result[0] === '0') return '0'
    
    return result
}

 

a, b의 솔팅 조건은 우선 a, b의 자릿수를 비교하는 코드로 진행된다.

자릿수가 같다면, 당연히 더 큰 수가 낮은 인덱스에 배치될 수 있도록 진행, 

자릿수가 같지 않다면, a,b를 문자형으로 이어 붙인 후 크기를 비교해보면서 우선순위 솔팅을 할 수 있도록 작성했다.

마지막에 result[0]에 대한 조건문이 들어간 이유는 join까지 마무리한 값이 '000'의 값으로 출력될 수 있기 때문에 추가로 작성한 코드이다.

시간복잡도 O(n)코드 완성! 통과!

 

2. H-Index. -> URL

 

문제

처음에는 문제를 제대로 파악을 못하고 좀 헷갈렸었다.

이 문제에서 말하는 h-Index에 대한 정의를 다시 확인해볼 필요가 있다고 느꼈다

h-index : 그 사람이 쓴 모든 논문 중 h회 이상 인용된 논문이 h개 이상일 때, 이 둘을 동시에 만족하는 h의 최대값으로 한다.

위 정의를 생각한다면 어렵지 않은 문제였다.

 

수도코드

그 사람이 쓴 모든 논문 중 n회 이상 인용된 논문이 n개 이상일 때, 이 둘을 동시에 만족하는 n의 최대값으로 한다.

배열을 우선 오름차순으로 정렬한다
h의 초기 최댓값은 논문의 갯수 (citations의 길이)

정렬한 배열을 순회한다
    validArr을 선언하고, 정렬한 배열에서 h의 값 이상을 갖는 논문들만을 필터링한다
    만약 논문의 갯수가 h이상이라면 h를 바로 리턴한다
    그렇지 않다면 h를 1 감소 시킨다

반복문이 끝나면 0을 리턴한다

 

풀이

function solution(citations) {
    const sortedCitations = citations.sort((a, b) => b - a);
    let h = sortedCitations.length
    
    for (const el of sortedCitations) {
        const validArr = sortedCitations.filter((item) => item >= h);
        
        if (validArr.length >= h) {
            return h;
        } else {
            h--;
        }
    }
    return 0
}

 

시간복잡도 O(n^2)의 코드를 구현했다.