[프로그래머스 42885] 구명보트 (Javascript)

👩🏻‍💻문제링크

[프로그래머스 42885] 구명보트 (Javascript)

✍️Idea Sketch

2021-07-12

1. 문제 이해

• 구명보트를 최대한 적게 사용

2. 몸무게 정렬

3. 로직

• 몸무게 작은 사람들끼리 모아서 보내기
• 몸무게 작은 사람, 몸무게 큰 사람 짝지어서 보내기

4. 문제점

• 몸무게 작은 사람들끼리 모아서 보내고 나면, limit/2가 넘는 사람들은 한명씩 보내야 함
• 몸무게 작은 사람, 큰 사람 짝지어서 보낼 경우 [50, 50, 70, 80] 입출력 예 1번을 만족하지 않음

5. 로직

• limit/2를 기준으로 두 분류로 나눔
• limit/2에서 left, right가 나옴 -> arr.indexOf(limit/2) 이거를 쓸 수도 없고 말이지..?
• 좌, 우에서 left, right
• sum이 limit보다 크면 --> right--, cnt++
• sum이 limit와 같으면 --> left++, right--, cnt++
• sum이 limit보다 작으면
  • sum += (left+1) 이 limit보다 작으면 left++, sum += left
  • sum += (left+1) 이 limit와 같으면 left++, cnt++
  • sum += (left+1) 이 limit보다 크면 left++, right--, cnt++

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

let cnt = 0;
let left = 0, right = arr.length-1;
let sum = arr[left] + arr[right];
let flag = false;

while(left <= right) {
  if (sum === limit) {
    cnt++;
    flag = false;
    sum = arr[++left] + arr[--right];
  }
  else if (sum > limit) {
    if (flag === false) {
      cnt++;
      sum = arr[left] + arr[--right];
    }
    else {
      cnt++;
      sum = arr[left] + arr[--right];
    }
  }
  else if (sum < limit) {
    sum += arr[++left];
    flag = true;
  }
}

6. cnt 로직

• Set()을 사용해 myset.delete(left), myset.delete(right)를 할까? --> 효율성문제 생길듯
• 인덱스 이동만 할까 left++ right--

✍️소스코드

2021-07-12 정확성, 효율성 통과

function solution(arr, limit) {
  let cnt = 0;

  arr.sort((a, b) => a - b);
  let left = 0, right = arr.length - 1;
  let sum = arr[left] + arr[right];
  let flag = false;  // sum에 left를 2번 이상 더한 경우 true

  while (left <= right) {
    if (left === right) return ++cnt;
    if (sum === limit) {
      cnt++;
      flag = false;
      sum = arr[++left] + arr[--right];
    }
    else if (sum > limit) {
      cnt++;
      flag = false;
      sum = arr[left] + arr[--right];
    }
    else if (sum < limit) {
      flag = true;
      sum += arr[++left];
    }
  }
  return cnt;
}

✍️명답

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