문제설명

설계 과정

풀이 코드

function solution(people, limit) {
    var answer = 0;
    if(people.length===1) return 1;
    
    // 내림차순으로 정렬
    people = people.sort((a,b)=>{
        return a>b? -1:1;
    })
    var boat;
    var exPeople;
    while(true){
        boat = 0;
        exPeople = people;
        for(var i =0;i<people.length;i++){
            if(boat+people[i]<=limit){
                exPeople.splice(exPeople.indexOf(people[i]),1);
                boat+=people[i];
            }
        }
        answer++;
        people = exPeople;
        if(exPeople.length===0){
            return answer;
        }
    };
}

결과

시간 초과 및 몇몇 케이스에서 실패가 떴다. 우선 시간초과가 발생했기 때문에 이러한 노가다식의 풀이 방법 대신 무언가를 써야 될 것이다.

개선 설계 과정

• 우선 people을 내림차순으로 정렬한다.
• 두명을 담당할 left, right 변수를 생성한다. -> left는 왼쪽부터, right는 오른쪽부터 체크

1. people[left] + people[right] 가 limit를 넘어간다면, 무거운 사람 한명만 구명보트에 태운다.
   -> left++
2. 넘어가지 않는다면, 그 두명을 구명 보트에 태움.
   -> left++, right--
3. 이후에 보트를 추가

• 위의 과정을 left>=right 일때까지 반복
• 만약 끝나고 left = right라면 중간에 값이 하나 남은거 있이기 때문에 이도 고려.

개선 코드

function solution(people, limit) {
    var answer = 0;
    // 내림차순으로 정렬
    people = people.sort((a,b)=>{
        return a>b? -1:1;
    })
    var left = 0;
    var right = people.length-1;

    while(left<right){
        //넘지 않는다면 이 둘을 채택
        if(people[left]+people[right]<=limit){
            left++;
            right--;
        }
        //넘는다면 무거운 사람 한명만 구명보트에 태움
         else{
            left++;
        }
        answer++;
    }
    //중간에 한명이 남았다면 그 사람 구명보트 태움
    if(right === left){
        answer++;
    }
    return answer;
}

우선 문제를 최대 두명이라는 것을 읽지 못했다..... 문제를 제대로 읽지 않았다..... 본인은 최대한 다 태울 수 있는 것이라고 생각했고 위에 처럼 코드를 구상한 것이다. 일단 여기에서 잘못이 있어서 몇개의 케이스가 틀린것 같다.
그리고 위에서 여러가지 함수를 사용하고, 배열을 새로 만들고 이러한 복잡한 코드를 구현했는데, 이렇게 index 값을 위와 같이 간단하게 생각한다면 시간복잡도도 좋게 할 수 있다.


이번 문제를 하면서 느꼈던게, 문제에서 하라는 대로 설계하고 코딩하는 대신 이 문제를 관통할 수 있는 문제풀이 방법이 있을 것이고, 이를 되도록 빠르게 파악하는 연습을 해야 될 것이라고 생각이 든다.