Programmers 구명보트 Javascript (Greedy)

cptkuk91·2022년 9월 15일
1

Algorithm

목록 보기
99/161
post-custom-banner

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=javascript

제한사항

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

풀이 코드

function solution(people, limit) {
	let count = 0
	let	left = 0
    let right = people.length - 1;
        
    let sorted = people.sort((a, b) => a - b);
    
    while(left < right) {
    	if(sorted[left] + sorted[right] <= limit){
        	left++;
            right--;
            count++;
        } else {
        	right--;
        }
    }
    return people.length - count;
}

기존 박스 문제와 비슷하다. (단어만 다를 뿐 똑같다.)

가장 왼쪽과 오른쪽 값을 구하기 위해서 정렬한다.

let + right <= limit이면 count++ 하고 그 다음으로 넘어간다.
left + right > limit 라면 right-- 를 한다. 왜냐하면 right 이외의 값을 더하면 limit보다 커지기 때문이다.

right의 경우 가장 끝자리부터 시작할 것이기 때문에, right = people.length - 1 된다.

특별히 어려운 부분은 없다.

profile
메일은 매일 확인하고 있습니다. 궁금하신 부분이나 틀린 부분에 대한 지적사항이 있으시다면 언제든 편하게 연락 부탁드려요 :)
post-custom-banner

0개의 댓글