[프로그래머스] 구명보트 (자바스크립트/ javascript/ js)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42885

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

 

 

 

문제를 해결하기 위한 아이디어

이 문제는 무인도에 갇힌 사람을 나타내는 people 배열이 최대 5만명이기 때문에 효율적인 방법으로 코드를 작성해야 한다. 처음에는 알고리즘다운 생각을 제대로 하지 못해서 이중 for문으로 가능한 경우의 수를 모두 도는 방법을 생각했는데, 이 문제는 효율성 점수도 있기 때문에 그렇게 해서는 풀 수 없는 문제인데다가 정확성부분에서도 틀리는 케이스가 많았다. 그래서 다른 분의 코드를 보고 많은 것을 배웠다.

people 배열을 우선 내림차순으로 정렬한 다음, left와 right라는 배열에서 각각의 요소를 가리키는 인덱스를 정의해서

맨 처음에는 left가 0을 가리키게 하고, right는 배열의 가장 끝 인덱스를 가리키게 한다.

그리고 반복문은 left보다 right가 클 때까지 반복문을 돈다. left와 right가 역전되거나 같아지는 순간 반복문을 탈출하는 것이다. 그렇게해서 맨 처음에 가장 큰 몸무게와 가장 작은 몸무게를 더해서 limit보다 큰지 따진다. limit보다 크다면 몸무게가 가장 많은 사람 혼자 보트를 타야 하므로 left를 하나 증가시킨다. 만약 두 사람의 몸무게 합이 limit보다 같거나 작다면 같이 보트를 탈 수 있는 것 이므로 이 경우 left는 하나 증가되고 right는 하나 감소된다.

조건문 다음에는 보트를 증가시키면 된다. (혼자 타게 되던, 같이 타게 되던 반복문 한 번에 무조건 보트는 하나 증가하게 되기 때문에)

그러다가 left와 right가 역전되면 상관 없는데 반복문이 끝났는데도 만약 left와 right가 가르키는 값이 같다면 마지막 한 사람은 안 세준게 되므로 이 경우 역시 보트를 하나 증가시킨다.

 

 

 

 

내가 작성한 코드 (자바스크립트)

function solution(people, limit) {
  let boat = 0;
  people.sort((a, b) => b - a);
  let left = 0;
  let right = people.length - 1;

  while (left < right) {
    if (people[left] + people[right] > limit) {
      left++;
    } else {
      left++;
      right--;
    }
    boat++;
  }
  if (left === right) boat++;
  return boat;
}