프로그래머스 정렬 문제풀이

자몽·2022년 1월 11일
1

알고리즘

목록 보기
22/31

K번째 수 - 프로그래머스

링크

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

풀이

slice 메서드를 사용해 array 배열을 원하는 부분만큼 잘라준다.

이후 잘려진 배열을 정렬시키기 위해 sort() 메서드를 사용한다.

여기서 주의할 점은, sort()만 사용할 경우, 10과 2가 있으면 10을 더 우선시 여기기 때문에,
sort((a,b)=>a-b)를 통해 정확하게 비교하도록 만들어야 한다.

마지막으로 정렬된 배열에서 원하는 요소를 찾아 answer에 push해준다.

전체 코드

function solution(array, commands) {
    const answer = [];
    
    for(let i=0;i<commands.length;i++){
        answer.push(array.slice(commands[i][0]-1,commands[i][1]).sort((a,b)=>a-b)[commands[i][2]-1])
    }
    return answer;
}

가장 큰 수 - 프로그래머스

링크

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

풀이

이 문제에서 가장 중요한 점은 숫자 313이 있다면 331313보다 크기 때문에 sort를 할 때, 31<3과 같이 판단해야 한다는 점이다.

이를 해결하기 위해 '31'+'3'의 결과인 313'3'+'31'의 결과인 331을 비교하였다.

해당 코드는 numbers.sort((a,b)=>(b + a) - (a + b))부분이다.

하지만, 이렇게 풀었을 경우 예외 처리를 하지 않았기 때문에 문제 제출 시 오류가 난다.
예외적인 경우는, 입력값으로 [0,0,0]과 같은 배열이 들어왔을 경우 return 값은 문자열이기 때문에 '0'이 아닌 '000'이 나올 때이다.
따라서 answer==0인 경우 '0'을 리턴하고, 아니라면 그대로 answer를 리턴하였다.

전체 코드

function solution(numbers) {
    const answer = '';
    numbers = numbers.map(number=>String(number))
    answer = numbers.sort((a,b)=>(b + a) - (a + b)).join('')
    return answer==0?'0':answer;
}

H-Index - 프로그래머스

링크

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

풀이

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

이 문제의 규칙을 찾으면 다음과 같다.

[3,0,6,1,5] input을 예시로 들어보겠다.

배열을 오름차순으로 정렬한 후, 가장 뒤에서부터 논문을 훑는다고 가정하자.
[0,1,3,5,6]

맨 뒤 논문 인용 횟수: 6번
훑은 논문 수: 1개

맨 뒤 -1 논문 인용 횟수: 5번
훑은 논문 수: 2개

맨 뒤 -2 논문 인용 횟수: 3번
훑은 논문 수: 3개

맨 뒤 -3 논문 인용 횟수: 1번
훑은 논문 수: 4개

우선 답은 3번 이상 인용된 논문이 3편 이상이므로 return으로 3이 나온다.

규칙을 찾아보면, 훑은 논문 수가 논문 인용 횟수보다 적어지기 직전이 이 문제의 답이 된다.

예외처리

훑은 논문 수가 논문 인용 횟수보다 적어지기 전 반복문이 종료되면, 단순히 훑은 논문 수가 H-Index가 되므로 return count를 해주어야 한다.

전체 코드

case 1: 내장된 sort() 메서드를 사용해서 풀이함.

function solution(citations) {
    citations=sort((a,b)=>a-b)
    let count = 0;
    for(let i=citations.length-1;i>=0;i--){
        count++;
        if(count>citations[i]){
            return --count;
        }
    }
    return count;
}

case 1: 병합 정렬을 구현해 풀이함.

function mergeSort(arr) {
    if(arr.length<2) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid)
    const right = arr.slice(mid)

    return merge(mergeSort(left),mergeSort(right))

    function merge(left,right){
        let result = []
        let leftPointer = 0;
        let rightPointer = 0;

        while(leftPointer<left.length && rightPointer<right.length){
            if(left[leftPointer]<right[rightPointer])   {
                result.push(left[leftPointer])
                leftPointer++;
            }else{
                result.push(right[rightPointer])
                rightPointer++;
            }
            //console.log(result)
        }
        return [...result,...left.slice(leftPointer),...right.slice(rightPointer)]
    }
}


function solution(citations) {
    citations=mergeSort(citations)
    let count = 0;
    for(let i=citations.length-1;i>=0;i--){
        count++;
        //console.log('count',count,'index',citations[i])
        if(count>citations[i]){
            return --count;
        }
    }
    return count;
}
profile
꾸준하게 공부하기

0개의 댓글