구명보트

내 풀이법

문제해석

• 구명보트에는 2명이하 탈 수 있으며, 2명의 몸무게가 limit을 넘어서는 안된다
• 2명이 탈 수 없다면 1명을 태워야한다
• 최소한의 구명보트 사용 개수를 구하라

 

내가 생각한 풀이법

• 몸무게가 가장 무거운 사람별로 나열한다
• 선택한 사람과 더하면 limit 이하지만 최대에 가까운 사람과 같이 탈 수 있도록 한다
• 구명보트에 탄 인원은 배열에서 지운다

나의 코드

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

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

  while (people.length > 0) {
    let partnerCandidate = [];
    for (let j = 1; j < people.length; j++) {
      if (people[j] + people[0] <= limit) {
        partnerCandidate.push(j);
      }
    }

    if (!!partnerCandidate[0]) {
      let candidate = partnerCandidate[0];
      answer++;
      people.splice(candidate, 1);
      people.splice(0, 1);
    } else {
      answer++;
      people.splice(0, 1);
    }
  }
  return answer;
}

 

코드특징

• 우선 몸무게 가장 큰 인원부터 나열
• 가장 큰 인원을 기준으로 같이 탈 인원을 for문을 통해 찾음
• 구명보트에 같이 타는 인원은 최대한 limit에 근접하도록 조건을 줌
• 구명보트에 탈 인원은 splice()를 사용하여 배열에서 삭제

 

코드성능

• 정확성에는 통과했지만 효율성에는 시간을 초과하여 좀 더 가벼운 모델이 필요하다
• 2중 for문을 사용해서 안되는 것으로 예상

 

다른사람 풀이법

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;
}

 

코드특징

 

• 가장 무거운 사람과 가장 가벼운 사람을 차례대로 짝지어 구명보트에 태우는 모델
• 두 인원이 구명보트에 탄 경우만 더하여 마지막에 전체인원에서 빼 정답을 구함

 

코드성능

 

• 정확성 및 효율성 통과

 

오늘 배운점

• 최대한 정확하게 코드를 작성하면 효율성에서 많이 부족한 경우가 나올 수 있다
• greedy 문제의 경우에는 최상의 수는 아니지만 정확성과 효율성을 동시에 잡을 수 있는 방법을 찾아보자