프로그래머스 / greedy / 구명보트

문제

---

 

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

프로그래머스

 

입출력

---

 

해설

---

 

문제를 정리하자면 다음과 같다.

 

1. 보트를 이용하여 모든 사람들을 구출해내는 것이다.

2. 보트의 정원은 최대 2명이다.

3. 보트의 한도 무게가 정해져 있는데 그것이 limit이다.

 

처음으로 떠올릴 수 있는 생각은 최대 2명씩 탈 수 있으므로 limit에 맞게끔 2명씩 짝지어주면 되지 않을까라는 생각을 할 수 있다.

 

해당 문제의 KeyPoint는 다음 예제일 것 같다.

 

people : [80, 70, 30, 20]

limit : 100

 

이렇게 된다면 (80, 20), (70, 30) 이런식으로 짝을 지어서 구출하면 될 것이다.

 

입력으로 저렇게 정렬이 된 상태로 들어오지 않을 수 있기 때문에 정렬을 하면 될 것이고, 이후 limit에 맞게끔 하면 되는데

limit에 맞게 짝을 어떻게 줄 수 있을까?

 

현재 짝을 지어준 형태를 보면 (가장 큰 값, 가장 작은 값), (그 다음으로 큰 값, 그 다음으로 작은 값) 이런 형태로 짝이 지어진 것을

볼 수가 있다.

 

정렬을 하게 되면 오름차순이든 내림차순이든 결국에는 한 방향으로 나열이 되는데, 이런 한 방향의 상태가 되기에 가장 큰 값과 가장 작은 값을 알 수 있게 되고 결국에는 짝을 지을 수 이게 된다.

 

만약 가장 큰 값과 가장 작은 값이 짝을 이룰 수 없다면 어떻게 되겠는가?

당연히 큰 값은 혼자서 보트를 타야 한다.

그 후 그 다음으로 큰 값과 가장 작은 값과 같이 구명보트를 탈 수 있는지 체크하면 된다.

정답코드

---

'''

'''
def solution(people, limit):
    answer = 0
    people.sort()
    
    front = 0
    
    back = len(people) - 1
    while back > front:
        if people[front] + people[back] <= limit:
            front += 1
        answer += 1
        back -= 1
        
    if front == back:answer += 1
    
    return answer

 

깃허브 : https://buly.kr/74X63Dq

유튜브 : X