[프로그래머스][JS] 구명보트 ✅

https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

풀이 과정

function solution(people, limit) {
    const sorted = people.sort((a, b) => b - a) // 내림차순 정렬
    let cnt = 0 // 보트를 사용한 횟수
    // start와 end는 sorted 배열에 인덱스로 접근
    let start = 0
    let end = people.length - 1
    while(start <= end){
        if (sorted[start] + sorted[end] <= limit){ // 가장 무거운 사람과 가벼운 사람의 합이 limit을 넘지 않는 경우
            start++
            end--
        }else{
            // 가장 무거운 사람만 보트에 탐
            start++
        }
        cnt++ // 위의 조건문을 통과할 때마다 +1
    }
    return cnt;
}

투 포인터 알고리즘을 사용하여 문제를 풀었다. 

people 배열을 내림차순으로 정렬한 뒤, 두 개의 포인터 start, end를 사용하여 처음과 끝을 가리키도록 한다.

두 포인터를 이용하여 가장 무거운 사람과 가장 가벼운 사람의 합을 구하여 limit과 비교하는 방식으로 문제를 해결했다.

 

sorted = [80, 70, 50, 50]  → people배열을 내림차순으로 정렬

 

가장 처음과 끝의 합이 limit을 넘으면 가장 처음 수 start에 +1을 하여 앞으로 이동시켜 준다

start = 0, end = 0, cnt = 0

sorted [start] = 80, sorted [end] = 50 → 130 > limit

start++ → start = 1

조건문을 통과하면 cnt++ → cnt = 1

 

sorted[start] = 70, sorted[end] = 50 → 120 > limit

start++ → start = 2

조건문을 통과하면 cnt++ → cnt = 2

 

가장 처음과 끝의 합이 limit을 넘지 않으면 start, end에 +1을 해준다

sorted [start] = 50, sorted[end] = 50 → 100 === limit

start++ → start = 3

end++ → end = 1

조건문을 통과하면 cnt++ → cnt = 3(정답!)

 

[이것이 코딩 테스트다: 투 포인터]: https://youtu.be/ttLRltNDiCo

---

리뷰

코드를 보면 쉬운데 스스로 생각해서 풀면 계속 시간초과가 발생하고 점점 어려워서 진도가 안나가진다...