[JS] 구명보트

 

 

난이도: Lv.2

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

프로그래머스

 

 

알고리즘

최선의 상황은 2명씩 타는 보트가 최대한 많은 것이다.

한 보트에 두 명씩 태울 때 최선은 가장 가벼운 사람과 가장 무거운 사람을 같이 태우는 것이다.

 

먼저, 사람들의 몸무게를 담은 배열 people을 정렬한다.

다음으로, 가장 가벼운 사람과 가장 무거운 사람이 같이 탈 수 있는지 확인해야 한다. 둘 중 가벼운 사람의 인덱스는 i, 무거운 사람의 인덱스는 j라고 하자.

1. 둘이 합쳐 limit을 넘으면 무거운 사람은 무조건 혼자 타야 한다. 무거운 사람이 혼자 타게 되면 보트 수를 1 증가시키고 배열에서 pop()하여 그 사람이 구출되었음을 명시한다.
2. 둘이 합쳐 limit을 넘지 않아서 같이 탈 수 있다면 두 명이 한 보트에 탔으므로 보트 수를 1 증가시킨다. 해당되는 두 사람이  구출되었음을 명시하기 위해 둘 중 무거운 사람은 pop()하고, i 인덱스를 다음으로 옮긴다.

이렇게 계속 진행하다 보면 누군가랑 같이 탈 수 있는 몸무게인데도 무인도에 혼자만 남아있는 상황이 생긴다. 이 상황이 i와 j의 값이 같아지는 경우이므로 i와 j 값이 같으면 혼자 보트에 태워 구출한다.

 

 

코드

function solution(people, limit) {
    var answer = 0;

    people.sort((a, b) => a - b);

    for (let i = 0; i < people.length; i++) {
        let j = people.length - 1
        for (; j > i; j--) {
            if (people[i] + people[j] > limit) { answer++; people.pop(); }
            else { answer++; people.pop(); break; }
        }
        if (j === i) { answer++; }
    }
    
    return answer;
}

 

 

주저리

한 번에 최대 2명씩만 탈 수 있는 거 모르고 여러 명 탈 수 있는 줄 알고 3시간 동안 삽질했다. 이게 정답률이 69%라고??? 내가 빡통이군 했다. 문제 제대로 안 읽은 것도 빡통이긴 해ㅎㅎ 2명만 탈 수 있는 거 깨닫고 질문하기 보다가 누가 O(n)으로 풀었다길래 얼레 정렬을 하면 안 되나(정렬하면 O(nlogn)) 했지만 그냥 정렬해서 풀고 그 사람 상세 보기 들어가서 봤는데 정렬하는 코드 때문에 O(n)이 아닐 수도 있지만 전체적인 흐름이 O(n)이라고 어그로 끌었던 것이었다.