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

 

이 문제는 '탐욕법'을 사용해야 합니다!

탐욕법이란 현재 상황에서 가장 좋은 선택을 하는 것을 말합니다. 탐욕법은 이미 알고리즘이 있기 때문에 알고리즘을 기반으로 코드를 작성해 보았습니다!

 

function solution(people, limit) {
    let answer = 0; 
    let sortedPeople = people.sort((a, b) => a - b) 

    while (sortedPeople.length !==0) { 
        if (sortedPeople[0] + sortedPeople[sortedPeople.length-1] <= limit) { 
            answer++ 
            sortedPeople.shift();
            sortedPeople.pop();
        } else {
            answer++
            sortedPeople.pop();  
        }
  }
    
  return answer; 
}

 

코드 설명!!

1. 탐욕법을 하기 위해서는 오름차순 정렬을 해야하기 때문에 sort()를 사용해 people 배열을 오름차순 정렬을 해줍니다.

2. sortedPeople 배열이 0이 아닐 때까지 -> 만약 조건이 맞는다면 sortedPeople 배열의 요소를 하나씩 제거해 줄 예정!

3. 조건

- 만약 sortedPeople 배열의 0번째 요소와 마지막 요소의 합이 limit보다 작다면 answer을 더해주고 더했을 때 참인 수를 지우기 위해 shift()와 pop()을 사용한다!

- 그게 아니라면 맨 마지막 값은 혼자서 limit을 채우기 때문에 pop()을 해줍니다! 

4. 이 과정을 반복하게 되면 sortedPeople 배열의 원소가 남지 않게 되고 결과값 answer를 리턴해주면 됩니다~!!

 

예제 - people = [70, 50, 80, 50],  limit = 100, sortedPeople = [50, 50, 70, 80]

1회 반복  -  50 + 80 <= 100 -> false => answer = 1, sortedPeople = [50, 50, 70]

2회 반복  -  50 + 70 <= 100 -> false => answer = 2, sortedPeople = [50, 50]

3회 반복  -  50 + 50 <= 100 -> true => answer = 3, sortedPeople = []

--- 반복 종료 ---

 

이 문제는 탐욕법을 모른다면 어렵겠습니다! 이 문제를 통해 탐욕법을 알았으니 다음 문제도 수월하게 풀 수 있을 것 같습니다!!! 

알고리즘 공부는 끝이 없다!!! 앞으로도 계속 꾸준히 하다보면 언젠가는 알고리즘을 마스터할 수 있다!! 화이팅~~ (●ˇ∀ˇ●)