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

문제 출처

프로그래머스 lev2 - 구명보트

나의 풀이

1차 시도 (시간 초과)

dfs로는 시간초과 발생한다..

function solution(people, limit) {
  let ch = Array.from({length:people.length}, () => 0);
  let tmp = [];
  let max = Number.MAX_SAFE_INTEGER;

  function Rescue (L) {
    if (L===people.length) {
      let cnt=0;
      let answer=[];
      for (let i=0; i<tmp.length; i++) {
        if (answer.length==0) {
          answer.push(tmp[i]);
        }
        else if (answer.length==1) {
          if (answer[0]+tmp[i] <= limit) {
            answer.shift();
            cnt++;
          }
          else if (answer[0]+tmp[i] > limit) {
            answer.shift();
            cnt+=2;
          }
        }
      }
      if (answer.length !== 0) cnt++;

      max = Math.min(max, cnt);
      // console.log(tmp, answer, cnt);
    }
    else {
      for (let i=0; i<people.length; i++) {
        if (ch[i]==0) {
          ch[i]=1;
          tmp[L]=people[i];
          Rescue(L+1);
          ch[i]=0;
          tmp.pop();
        }
      }
    }
  }
  Rescue(0)
  return max;
}

console.log(solution([70, 50, 80, 50], 100));

다른 풀이

그리디 알고리즘

시작점과 끝지점을 설정하고,
구명보트에 최대 2명씩 밖에 탈수 없기 때문에 가장 많이 탈 수 있는 방법은 가장 무거운 사람과 가장 가벼운 사람이 타는 방법 뿐임.

function solution(people, limit){
	var answer = 0
  people.sort((a,b) => b-a)
  let l = 0
  let r = people.length-1
  
  while(l<r){
    var sum = people[l] + people[r]
      if(sum>limit){
        l++ // 혼자 탄 배 answer++;
      } else {
        l++ // 함께 탄 배 answer++;
        r--
      }
      answer++
  }
  if(l == r) answer++ // 계산되지 않은 애는 혼자타는 배로 answer++;
  return answer
}

console.log(solution([70, 50, 80, 50], 100));

호이스팅(var i)을 활용한 풀이

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

console.log(solution([70, 80, 50], 100));