[Javascript] 구명보트 (42885)

문제링크

코딩테스트 연습 - 구명보트

 

 

접근방법

그리드 문제로 가장 조건에 가까운 경우를 판단하는 문제이다.

주어진 people 배열을 정렬하여 제일 가벼운 사람과 제일 무거운 사람을 선택하여 
limit보다 작으면 옮기고, limit보다 크면 무거운 사람만 옮기는 방식으로 진행하였다.

배운점

처음 풀이한 문제가 효율성 테스트에서 계속 탈락하였다.

people.shift를 사용하여 배열의 제일 앞 요소를 제거한 것이 문제였는데,
배열은 제일 앞 요소를 제거할 시 Index 번호를 처음부터 다시 지정해주는 비효율적인 작업이 필요하다.

때문에 people 배열을 직접 건드리지 않고 Index번호만 증감하는 방식으로 접근하였다.

// 처음 풀이
// 효율성 탈락

function solution(people, limit) {
  var answer = 0;
  people.sort((a, b) => a - b);

  while (people.length) {
    if (people[0] + people[people.length - 1] > limit) {
      people.pop();
      answer++;
    } else {
      people.pop();
      people.shift();
      answer++;
    }
  }

  return answer;
}

// 수정한 풀이
// 효율성 통과

function solution(people, limit) {
    var answer = 0; 
    let lightPerson = 0;
    let heavyPerson = people.length - 1;
    people.sort((a,b) => a-b);
    
    while(lightPerson <= heavyPerson){
        if(people[lightPerson] + people[heavyPerson] > limit){
            heavyPerson--;
            answer++;
        }else{
            heavyPerson--;
            lightPerson++;
            answer++
        }
    }

    return answer;
}