[Programmers Level 2 탐욕법] 구명보트 Javascript

문제정보

 

 

탐욕법으로 푸는 문제인데 제 풀이가 탐욕법이라고 할 수 있을지가 의문이네요..

---

😋 접근방법

구명보트를 최대한 적게 쓰면서 구명보트는 최대 두명밖에 탈 수 없다.

가장 좋은 방법은 limit을 꽉꽉채워서 2명씩 태워보내는것일겁니다.물론 한명밖에 탈 수 없는 경우엔 한명씩 태워 보내야겠지요

 

가장 무거운 사람과 가장 가벼운 사람의 무게합이 limit보다 작다면 그게 베스트케이스라고 생각했습니다.

반면 가장 무거운사람이 가장 가벼운 사람과 같이 타도 limit을 넘는다면

가장 무거운 사람은 혼자 보트를 탈 수 밖에 없을것입니다.

 

---

 

나의풀이

 

function solution(people, limit) {
    people.sort((a,b) => a - b)
    let left = 0
    let right = people.length-1
    let answer = 0
    
    while(left <= right) {
        if(people[left] + people[right] <= limit) {
            answer += 1;
            left += 1
            right -= 1
        }
        else{
            answer += 1
            right -= 1
        }
    }
    return answer
}

 

 

투포인터 방식으로 구현했습니다.

left와 right 그리고 보트의 갯수를 저장해줄 answer 변수를 선언해준 뒤

left와 right가 서로 만나게될때까지 while문을 돌려줬습니다.

 

left는 배열의 앞쪽부터 right는 배열의 뒷쪽부터 접근해나가면서

두 사람이 같이 탈 수 있는 경우엔 같이 태웠고

 

그렇지 않은 경우엔 가장 무거운 사람 한명만 보트에 태워 보내면서

보트 수를 세어줬습니다.