[Lv2] 구명보트

프로그래머스

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

나의 풀이(1) 효율성 테스트 통과 ❌

이 문제는 탐욕 알고리즘 중 짐 나르기 문제와 동일한 풀이여서 배열을 사용해 쉽게 풀었다. 그런데, 효율성 테스트를 하나도 통과하지 못했다.

function solution(people, limit) {
  let boat = 0;
  people.sort((a,b) => b-a);
  
  while(people.length) {
    boat++;
    const person = people.shift();
    if(person+people[people.length-1]<=limit) {
      people.pop();
    }
  }
  return boat;
}      

나의 풀이(2) 효율성 테스트 통과 ⭕ (투 포인터)

다른 풀이로 투 포인터를 작성해보았는데, 효율성 테스트가 모두 통과되었다.짐 나르기 문제에서 사용한 두 번째 풀이법을 떠올리며 풀었다.

function solution(people, limit) {
  people.sort((a,b) => b-a);
  let leftIdx = 0; //가장 무거운 사람 
  let rightIdx = people.length-1; //가장 가벼운 사람
  let boat = 0;
  
  while(leftIdx<rightIdx) {
    boat++;
    if(people[leftIdx]+people[rightIdx]<=limit) {
      rightIdx--;
    }
    leftIdx++;
  }
  if(leftIdx===rightIdx) boat++;
  return boat;

투 포인터

정렬된 배열을 두개의 포인터를 이용해 값에 순차적으로 접근한다. 두 포인터를 이동하며 두 개의 합 또는 연산결과를 비교하며 문제를 해결하는 알고리즘 패턴이다.

예제

특정 숫자들이 들어있는 배열이 주어졌을 때, 배열 안에 가장 첫 번째로 두 숫자의 합이 0이 되는 값 2개를 배열에 담아 리턴하는 함수를 만들어라. (값이 없다면 false를 리턴할 것)

• 이중반복문을 사용한 풀이 👉 시간복잡도 O(N^2)

function getZero(arr) {
  for(let i=0; i<arr.length; i++) {
    for(let j=i+1; j<arr.length; j++) {
      if(arr[i]+arr[j] === 0) {
        return [arr[i], arr[j]]
      }
    }
  }
  return false;
}

• 투 포인터를 사용한 풀이 👉 시간복잡도 O(N)
  이중반복문이 아닌 하나의 반복문으로 문제를 해결할 수 있다.

function getZero(arr) {
  arr.sort((a,b) => a-b); //오름차순 정렬
  let leftIdx = 0; //가장 작은 수 
  let rightIdx = arr.length-1; //가장 큰 수
  
  while(leftIdx<rightIdx) {
    const sum = arr[leftIdx]+arr[rightIdx];
    if(sum === 0) {
      return [arr[leftIdx], arr[rightIdx]];
    }
    if(sum < 0) { //합이 0보다 작다면, leftIdx를 오른쪽으로 옮긴다
      leftIdx++;
    } else { //합이 0보다 크다면, rightIdx를 왼쪽으로 옮긴다
      rightIdx--;
    }
  }
  return false;
}