[알고리즘/프로그래머스/고득점Kit] 정렬(JS)(K번째수, 가장 큰 수, H-Index)

문제: K번째 수

---

https://school.programmers.co.kr/learn/courses/30/lessons/42748?language=javascript 

프로그래머스

 

풀이

---

function solution(array, commands) {
    // (i-1)부터 j까지 자르고 정렬 -> k번째 숫자 
    return commands.map(([i, j, k]) => array.slice(i-1, j).sort((a, b) => a - b)[k-1])
}

 

---

 

문제: 가장 큰 수

---

https://school.programmers.co.kr/learn/courses/30/lessons/42746?language=javascript 

프로그래머스

 

풀이

---

function solution(numbers) {
    const num = numbers.map(n => n + '').sort((a, b) => {
       return (b + a) - (a + b)
    }).join('')
    return num[0] === "0" ? "0" : num
}

b+a와 a+b를 비교해 내림차순 정렬한다. sort는 compareFn의 반환값이 양수면 자리를 바꾸고(b, a), 음수면 그대로 둔다(a, b). 

여기서 a, b는 순차적으로 들어오는 값이 아니라 자바스크립트 엔진의 알고리즘이 결정한다. 

(b+a)가 더 크면 그대로, (a+b)가 더 크면 a, b의 자리를 바꾸는 식으로 동작해 항상 이어 붙인 숫자가 더 큰 순으로 나열되게 된다. 

또한 마지막 줄은 "00"과 같은 경우에 "00"이 아닌 "0"이 반환되도록 하는 코드이다. 

 

처음에는 마지막 줄 대신 숫자로 변환했다가 다시 문자열로 변환하도록 아래처럼 작성했는데 테스트케이스를 통과하지 못했다.. 왜 그런지 모르겠다. 

function solution(numbers) {
    return numbers.map(n => n + '').sort((a, b) => {
       return (b + a) - (a + b)
    }).join('') * 1 + '' 
}

문제에 질문을 남겨뒀는데 어떤 분이 답해주셔서 알게 되었다. 

 

 

---

 

문제: H-Index

---

https://school.programmers.co.kr/learn/courses/30/lessons/42747?language=javascript 

프로그래머스

 

풀이

---

처음에 문제를 잘못 이해하고 citations에 있는 값만 가능한 정답이라고 생각을 했다.. 그래서 가능한 모든 값을 확인하지 않고, citations 배열의 값만 확인해서 틀렸다. 질문 섹션을 보니 최댓값부터 하나씩 내려오면서 h가 가능한지 보면 될 것 같아서 그렇게 해봤다.

 

우선 문제 자체도 좀 헷갈리니 다시 살펴보자. 

n편 중 h번 이상인 값이 h편 이상 있으면 그게 h의 최댓값이다. 이게 무슨 말인지는 예제와 함께 살펴보자. 

예를 들어, [3, 0, 6, 1, 5]라는 배열이 있으면 먼저 내림차순으로 정렬해 [6, 5, 3, 1, 0]을 만든다.

 

1) cur(현재 값) === 6

6이상 값이 6번 배열에 존재해야한다는 건데, 배열 길이가 5이니 불가능하다. 

여기에서 최댓값은 항상 배열의 길이로 잡으면 된다는 걸 알 수 있다. 

2) cur === 5

5이상인 값이 5번 배열에 존재해야한다는 건데, 배열 길이가 5이니 5 이상인 값의 개수를 한 번 세본다. 

세어 보면 5 이상인 값이 5, 6으로 2개 밖에 없으니 다음으로 넘어간다.

3) cur === 4 

배열에 있는 값은 아니지만 4이상인 값이 4개 이상 존재하면 그게 답이니 하나씩 체크해야한다. 

4개 이상인 값은 5, 6으로 2개이니 넘어간다.

...

...

이런 식으로 하나씩 확인하다가 cnt가 현재 값인 cur 이상이 되면 return 해주면 된다. 

function solution(citations) {
    const len = citations.length
    // h가 가능한 최댓값부터 반대로 확인(i가 h)
    for (let i=len;i>=0;i--) {
        let cnt = 0
        for (let j=0;j<len;j++) {
            // i편 이상인 값 세기 
            if (i <= citations[j]) cnt += 1
        } 
        // i번 이상이면 
        if (i <= cnt) return i
    }

}

 

sort는 compareFn 넘겨주는 게 헷갈린다..🥹 양수면 자리를 바꿔서 음수면 순서대로, 0이면 그대로인 걸 기억하고, 오름차순이면 (a - b)를, 내림차순이면 (b - a)를 해주자.