[프로그래머스] 구명보트 (탐욕법)

https://school.programmers.co.kr/learn/courses/30/lessons/42885

접근

• boat 초기값을 사람수만큼 설정
• 몸무게가 높은 순으로 내림차순 정렬
• 가장 무거운 사람과 가장 가벼운 사람을 더한 값만을 이용
  • 값이 제한보다 큼 -> 무거운 사람은 혼자서밖에 못탐 배열에서 삭제 shift()
  • 값이 제한과 동일 -> 무거운 사람과 가벼운 사람을 배열에서 삭제(shift(),pop()), 필요한 보트 -1
  • 값이 제한보다 작음 -> 무거운 사람의 값에 가벼운 사람의 값을 더한후 가벼운 사람을 삭제, 필요한 보트 -1

function solution(P, limit) {
  P.sort((a, b) => b - a);
  let boat = P.length;

  while (P.length > 1 && P[P.length - 2] + P[P.length - 1] <= limit) {
    if (P[0] + P[P.length - 1] > limit) {
      P.shift();
    } else if (P[0] + P[P.length - 1] == limit) {
      P.shift();
      P.pop();
      boat--;
    } else {
      P[0] += P[P.length - 1];
      P.pop();
      boat--;
    }
  }

  return boat;
}

그 외에 시도한 것

• while문이 쓸데없이 많이 반복되는듯 하여 조건을 더욱 까다롭게 바꿈

  • && P[P.length - 2] + P[P.length - 1] <= limit (가장 가벼운 두명을 합한 것이 제한보다 작을때 반복)
  • while문 조건에 위 내용을 추가하여 반복을 줄임
  • 효율성 테스트에서 저 2개라도 맞게 됨..

• while문이 순차적으로 하나씩만 실행되는 것 때문에 오래 걸리나 싶어서 재귀함수 방식으로도 도전

  
  시간초과도 아니고 런타임 에러로 바뀌었다.

해결

• 한 4-5시간을 잡고 있다가 도저히 풀리지 않아서 질문게시판을 열었다.

  
  shift가 배열의 앞에서부터 삭제하고 뒤에 애들을 끌어오는거라 시간복잡도가 높은 함수라는 걸 알게 됨 !!!

function solution(P, limit) {
  P.sort((a, b) => b - a);
  let boat = P.length;

  let i = 0;
  while (i < P.length - 1) {
    if (P[i] + P[P.length - 1] > limit) {
      i++;
    } else if (P[i] + P[P.length - 1] == limit) {
      i++;
      P.pop();
      boat--;
    } else {
      P[i] += P[P.length - 1];
      P.pop();
      boat--;
    }
  }

  return boat;
}

• 기존의 while문 조건 대신 i를 이용 (완전탐색 형식)
• P[0]만을 확인 하면서P.shift();로 맨앞 원소를 삭제하던 것을
• P[i]를 확인하고 i++로 인덱스를 높이는 것으로 변경

마무리

몇시간을 해도 안되는 걸 오기로 별다른 아이디어 없이 조금씩 바꾸는 것은 시간낭비일 확률이 크고
차라리 구글링이나 아이디어가 떠오를 때까지 쉬다 오는 것도 방법인 듯 하다.