꒰ྀི 03. 프로그래머스:: 구명보트

문제 설명

 

구명보트를 이용해 무인도에 갇힌 사람 구조

한 번에 최대 2명씩 탈 수 있으며 무게 제한이 없음.

 

몸무게 배열 people과 구명보트의 무게 제한 limit가 주어질 때,

모든 사람을 구출하기 위핸 구명보트 개수의 최솟값을 구해야 함.

 

자료 구조

 

최대 2명씩 타기 위해 무거운 사람과 가벼운 사람을 함께 태워야함.

따라서 탐욕법을 이용해 매 단계에서 가장 좋아보이는 선택을 함.

 

문제 해결 과정

 

1. 먼저 몸무게 배열(people)을 오름차순으로 정렬함

 

2. 두 개의 포인터를 사용해 배열의 시작과 끝을 설정함

 

3. 포인터를 각각 이동시키며 보트 사용 횟수를 증가시킴

function solution(people, limit) {
    people.sort((a, b) => a - b);
    
    let left = 0;
    let right = people.length - 1;
    let boats = 0;

    while (left <= right) {
        if (people[left] + people[right] <= limit) {
            left++;
        }
        right--;
        boats++;
    }

    return boats;
}

 

각 단계에서 최선의 선택을 하기 위해 탐욕법을 사용했음.

어떻게 탐색할까 방법을 고민하던 도중, 포인터를 활용할 방안이 떠올랐음.

 

이 부분을 구현하는 것이 가장 어려웠음.

---

그런데 훨씬 간결하고 효율적인 코드가 있었다.

function solution(people, limit) {
    people.sort(function(a, b){return a-b});
    for(var i=0, j=people.length-1; i < j; j--) {
        if( people[i] + people[j] <= limit ) i++;
    }    
    return people.length-i;
}

 

for 루프와 if 조건을 이용해 불필요한 연산을 줄이고,

구명보트의 개수를 효과적으로 계산했다.

 

두 코드는 같은 논리지만, 훨씬 더 간결해졌다.

 

왜 var인가?

 

for 루프 내에서 i와 j의 스코프 차이로 var을 사용해야 한다.

 

let은 블록 스코프를 가지기 때문에,

for 루프 안에서 var과 다른 스코프로 작용한다.

var let const의 차이(호이스팅과 스코프)

 

개인적으로 코드가 조금 길어도 var을 사용할 생각은 없기 때문에 그냥 본래 코드대로 갈 예정이다.