[프로그래머스] 구명보트 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

리스트의 형태로 해결하려고 하였지만 리스트는 연산 속도가 느려 자꾸 시간초과가 생겼다. 하여 deque의 형태로 해결하였다.

이 문제는 구명보트에 최대 2명까지 태울 수 있으므로 가장 가벼운 사람과 가장 무거운 사람을 태웠을 때 무게 제한을 넘지 않으면 2명을 태우고 무게 제한을 넘는다면 가장 무거운 사람은 혼자 타고 가는 방식으로 해결한다.

 

1. deque을 사용하기 위해 collections 모듈에서 deque을 불러온다. from collections import deque
2. 입력받은 사람들의 몸무게를 오름차순으로 정렬한다. people.sort()
3. 오름차순으로 정렬한 몸무게를 deque 자료로 바꿔준다. people = deque(people)
4. 가장 무거운 사람을 나타낼 변수를 생성하고 가장 마지막 인덱스 값을 넣어준다. i = len(people) - 1
5. 모든 사람을 구출할 때까지 반복한다. while (len(people) != 0)
6. 만약 가장 가벼운 사람과 가장 무거운 사람의 몸무게를 더했을 때 구명보트의 무게 제한보다 같거나 작으면 if (people[0] + people[i] <= limit)
7. 두 명을 함께 구출한다. people.pop()  people.popleft()
8. 두 명이 구출되었으므로 다시 가장 무거운 사람의 인덱스 값을 바꿔준다. i = len(people) - 1
9. 구명보트가 사용되었으므로 구명보트 사용 개수에 1을 더한다. answer += 1
10. 반면에 가장 가벼운 사람과 가장 무거운 사람의 몸무게를 더했을 때 구명보트의 무게 제한보다 크면 else
11. 가장 무거운 사람은 어떤 경우에서든 혼자 구출되므로 혼자 나간다. people.pop()
12. 구명보트가 사용되었으므로 구명보트 사용 개수에 1을 더한다. answer += 1
13. 가장 무거운 사람이 구출되었으므로 가장 무거운 사람의 인덱스 값을 1 빼준다. i -= 1
14. 만약 가장 무거운 사람의 인덱스 값이 가장 가벼운 사람이면 (남은 사람이 1명이면) if (i == 0)
15. 남은 1명을 구출한다. people.popleft()
16. 구명보트가 사용되었으므로 구명보트 사용 개수에 1을 더한다. answer += 1

반응형

3. 소스코드

from collections import deque

def solution(people, limit):
    answer = 0
    
    people.sort()
    people = deque(people)
    
    i = len(people) - 1
    while (len(people) != 0):
        if (people[0] + people[i] <= limit):
            people.pop()
            people.popleft()
            i = len(people) - 1

            answer += 1
        else:
            people.pop()
            answer += 1

            i -= 1
            
        if (i == 0):
            people.popleft()
            answer += 1
        
    return answer