[프로그래머스 / JavaScript] 구명보트

-- 문제

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

프로그래머스

---

-- 최초 풀이

function solution(people, limit) {
    let cnt = 0;
    people.sort((a, b) => a - b);
    
    while (people.length >= 2) {
        if (people[0] + people[people.length - 1] <= limit) {
            people.pop();
            people.shift();
        }
        else {
            people.pop();
        }
        
        cnt++;
    }
    
    return cnt + people.length; // 여기서 people.length는 0 or 1
}

---

-- 접근 방법

people 배열을 오름차순 정렬한 후,

people.length 가 2 미만이 될 때까지 (1명 남으면 혼자 배 타고 가면 되므로 최종 결과에 +1 만 하면 됨) while loop 한다.

 

(case 분류)

1. people의 첫 원소와 마지막 원소의 합이 limit을 넘지 않는다 => 2명이 탈 수 있음 => pop(), shift() 연산

2. limit을 넘는다 => 2명이 탈 수 없음 => pop() 연산

 

그리고, cnt++ 을 loop 마지막에 해준다.

 

핵심은 "가장 최소로 배를 움직이려면 최대한 무거운 사람과 가벼운 사람을 보내도록 해야 한다" 였다.

---

-- 다른 풀이

주어진 배열의 크기가 매우 큰 경우, 부분 배열의 합을 구해야 하는 문제에서

투 포인터 알고리즘을 사용하면 더 효율적이라고 한다.

투 포인터 알고리즘은 완전 탐색에서 경우의 수를 효율적으로 탐색할 수 있게 해준다.

function solution(people, limit) {
    let cnt = 0;
    people.sort((a, b) => a - b);
    let start = 0; // 시작 포인터
    let end = people.length - 1; // 끝 포인터
    
    // 시작 포인터와 끝 포인터가 유효할 때까지 loop
    while (start < end) {
        if (people[start] + people[end] <= limit) {
            start++;
        }
        
        end--;
        cnt++;
    }
    
    return cnt + (end - start + 1);
}

 

이번 문제의 경우에는 성능 면에서 큰 차이가 나지 않았지만,

shift() 는 시간복잡도가 O(n), 즉 배열의 크기만큼의 시간이 걸린다.

people 원소 범위가 이보다 더 커지면 시간 초과가 날 수 있음을 유의해야 겠다.

 

-- 참고 링크

https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md

Ready-For-Tech-Interview/Algorithm/투포인터 알고리즘.md at master · WooVictory/Ready-For-Tech-Interview