[JS] [Programmers] 구명보트

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

• 프로그래머스 코딩테스트 연습 탐욕법 Level 2 문제입니다.

 

나의 풀이

---

function solution(people, limit) {
    let answer = 0;
	
    //오름차순 정렬
    people.sort((a, b) => a - b);

    while (people.length > 0) {

        let min = people[0]; // 가장 작은 무게
        let max = people.pop(); // 가장 큰 무게

        if (min + max <= limit) {
            people.shift();
        }
        
        answer += 1;

    }

    return answer;
}

 

풀이 순서

---

1. 보트는 한 번에 최대 2명이 탈 수 있으며, 이 때 필요한 최소한의 구명보트의 수를 구하는 문제입니다.
   
   
   1. 최대 2명만 탈 수 있을 때 최소한의 구명보트를 사용하려면 가장 낮은 뭄무게, 가장 큰 몸무게 두 사람씩 타면 최소한의 구명보트를 사용할 수 있습니다.
      
2. 몸무게 비교를 위해 주어진 사람들의 몸무게 배열(people)를 오름차순 정렬합니다.
   
   
   1. 가장 작은 몸무게는 배열의 첫번째 인덱스이며, 가장 큰 몸무게는 마지막에 위치합니다.
      
      
3. 가장 큰 몸무게를 빼주면서(pop) 만약 현재 가장 작은 몸무게와 합쳤을 때 보트 제한 무게를 넘지않으면 가장 작은 몸무게 또한 빼줍니다. (shift)
   
   
   1. 가장 큰 몸무게를 무조건 빼주면서 반복하는 이유는 예를 들어 [10, 20, 50, 70] 무게 배열이 있고 제한이 70일 때 작은 값을 빼면서 반복시 [ 10, 20, 50, 70 ] 으로 빠져 4개의 보트가 필요하고 큰 값을 빼면서 반복시 [ 70, 10+50, 20] 으로 빠져 3개의 보트가 필요하기 때문입니다.
      
      
4. 몸무게 배열의 길이가 0이되면 모든 사람이 보트에 탄 것이기 때문에 반복을 종료합니다.

 

다른 사람의 풀이

---

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

• 몸무게 배열을 오름차순 정렬하고 최댓값(people.length-1)부터 최솟값 인덱스보다 큰 경우까지 반복하며 만약 현재 배열의 최소+최대 무게가 제한 무게보다 작은경우 기준 최소 무게 인덱스를 ++ 해줍니다.
• 차이점
  
  
  • 나의풀이
    
    
    • 배열의 push(), pop()연산을 통해 구현
      
      
  • 다른 사람의 풀이
    
    
    • for문에 변수2개를 사용하여 구현

 

 

for문을 통해 간단하게 구현하는 방법이 있었는데 아쉽다! 반복문을 다채롭게 사용할 수 있도록 노력하자!!