[프로그래머스] 구명보트 - Javascript (Lv.2)

📖 문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

✔️ 제한조건

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

 

💻 나의 코드

function solution(people, limit){
    let cnt = 0; // 보트의 개수를 담을 변수 초기화
    people.sort((a, b) => b - a); // people 변수를 내림차순으로 정렬 (큰 것부터 작은 것순)
    let left = 0; // 왼쪽 인덱스 지정할 left변수를 0을 초기화 (인덱스는 0부터 시작하기에)
    let right = people.length - 1; // 오른쪽 인덱스를 지정한 right변수를 people의 길이 - 1로 초기화
    let seated = []; // 앉은 사람의 무게를 기록할 배열 변수 초기화
    
    // seated.length가 people.length와 같거나 커질 때까지 반복 수행
    // 같으면 보통 멈춰짐
    while(seated.length < people.length){
        let weight = people[left] + people[right]; // people[left]와 people[right]를 더한 값을 weight에 초기화
        if(limit < weight){ // 무게 제한보다 weight가 크면
            seated.push(people[left]); // seated에 people[left]값 넣어줌
            left++; // left를 1증가 (현재 left인덱스의 값을 위에서 push했기에 인덱스를 이동)
        }else{ // weight가 무게 제한 이하면
            left++; // left를 1증가
            right--; // right를 1감소
            seated.push(people[left]);  // seated에 people[left]값 넣어줌
            seated.push(people[right]); // seated에 people[right]값 넣어줌
        }
        cnt++; // cnt를 1 증가
    }
    return cnt; // cnt를 return
}

 

🎤 코드 설명

접근방법 : 받은 사람들의 무게를 내림차순 정렬해서 양 끝 값부터 하나씩 처리하는 방식을 사용했습니다. 

• 보트의 개수를 count할 변수 cnt를 초기화합니다. 
• 사람들의 무게를 담은 배열 변수 people를 sort를 사용해서 내림차순 정렬합니다. (a - b : 오름차순)
• left는 0으로 right는 people.length-1로 초기화합니다. (양 극단의 인덱스를 초기화한 것)
• 보트에 앉은 사람들의 무게를 기록할 seated배열 변수를 초기화합니다.
• seated.length가 people.length 미만일 때만 while반복문을 수행합니다.
  • weight에 people[left]와 people[right]를 더한 값을 초기화합니다.
  • weight가 무게 제한(limit)보다 크면
    • seated에 people[left]값을 넣고 left에 1을 더해 인덱스를 이동시킵니다.
  • weight가 무게 제한(limit) 이하이면
    • seated에 people[left] + people[right] 값을 넣고 left에 1을 더하고, right에서 1을 빼서 인덱스를 이동시킵니다
  • cnt를 1 증가시킵니다.
• cnt를 return합니다. 

 

📜 채점 결과

정확성: 75.0

효율성: 25.0

합계: 100.0 / 100.0

 

💬 배운 것

• 문제를 막상 봤을 때 난이도가 높아 보였지만, 정렬을 한다는 생각만 하면 쉽게 인덱스를 사용해서 풀 수 있는 문제였습니다. 
• limit와 weight의 비교에 따라 한 번에 2명이 탑승할 수도, 1명이 탑승할 수도 있다는 것을 고려해야 했습니다.

 

 

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