[프로그래머스 탐욕법]구명 보트- Python3

문제

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

코딩테스트 연습 - 구명보트 | 프로그래머스

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 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

 

알고리즘

def solution4(people, limit):
    from _collections import deque

    answer = 0
    people.sort()

    # dq는 배열의 양 끝에서 삽입, 삭제가 가능한 자료구조이다.
    dq = deque(people)

    while dq:
        length = len(dq)
        # dq에 원소가 2개 이상 있으면 삭제할 원소를 찾는다.
        if length >= 2:
            # 배열의 맨 처음과, 맨 끝의 원소를 더한 값이 limit보다 작다면, 맨 처음 원소와 맨 끝 원소를 pop한다.
            # 맨 끝 원소는 그냥 pop()으로 빼면 되지만,
            # 0번째 원소는 pop(0)으로 꺼낼 경우, people의 길이만큼의 시간복잡도를 갖는다.
            # 따라서, dq.popleft()로 꺼낸다. 이 경우, 시간 복잡도가 현저히 줄어든다.
            if dq[0] + dq[-1] <= limit:
                dq.popleft()
                dq.pop()
                answer += 1
            # 배열의 맨 처음과 맨 끝 원소의 합이 limit을 넘긴다면, 맨 끝 원소를 pop한다.
            else:
                dq.pop()
                answer += 1

        # dq에 원소가 1개밖에 없다면, answer에 1을 더해서 리턴한다
        elif length == 1:
            return answer + 1

        # dq에 원소가 없다면, answer를 리턴한다.
        else:
            return answer
    return answer
    
people = [10, 20, 30, 40, 50, 60, 70, 80, 90]
limit = 100

설명

정말 고민을 많이 했다. 아마 알고리즘 초보들은 거의 다 나처럼 생각했을 것이다. 내가 처음 생각한 답은,일단 people리스트를 오름차순으로 정렬을 한 다음에, 0번째 원소의 값이 limit을 넘지 않는다면, 0번째 원소의 값을 temp에 저장하고, 인덱스 j를 하나 더 추가해서, temp + people[j] <= limit 이 되는 최대값을 찾는 방법을 생각했을 것이다(즉, 인접한 원소의 값을 비교한다는 이야기이다). 그런데 이렇게 푸는 경우, 다음의 반례가 있다.

people = [10, 20, 30, 40, 50, 60, 70, 80, 90]
limit = 100

이 경우, 정답은 5 이다. 그러나 위에서 처럼, 인접한 원소들의 값을 바탕으로 배열에서 pop을 할 경우, 정답은 6이 된다. 그러니까 이 방법은 쓰면 안되는 방법이다. 

그렇게 한참을 고민하면서 다른 사람이 올린 질문을 보다가, 위에 기술한 알고리즘처럼, 첫 번째 원소의 값과 마지막 원소의 값을 보고 구명 보트에 태우는 알고리즘을 만들게 되었다. 최소값과 최대값을 합쳐서 limit을 넘는다면, 그 최대값은 어떤 다른 원소와도 같이 구명보트에 태울 수 없을 만큼 크다. 따라서, 그 원소를 pop하고, answer를 1 증가시킨다

최소값과 최대값을 합쳐서 limit을 넘지 않는다면, 두 원소를 같이 보트에 태울 수 있다. 따라서, people에서 popleft. pop을 해준다. 

그리고, 원래는 dequeue를 쓰지 않고 list를 써서, pop(0)과 pop()을 썼는데, 이 경우 시간 복잡도가 올라간다. 왜냐하면, pop(0)을 할 경우, people[0]의 값을 temp에 넣어두고, people[1]의 값을 people[0]으로, people[2]의 값을 people[1]로 복사한다. 그렇기 때문에, O(N)의 시간 복잡도가 추가된다. 그러나 dequeue를 쓰면 양쪽 끝에서 입출력이 가능하므로 실행 시간을 훨씬 줄여줄 수 있다. 

자료구조 deque

알고리즘은 다음과 같다.

1. people배열을 sort()한다. 
2. 정렬된 people배열을 dequeue자료구조로 만들어서, dq에 저장한다. 
3. dq의 원소가 있는 동안
   1. dq의 원소의 갯수가 2보다 크다면, 
      1. dq[0] + dq[-1] <= limit인지를 보고, 
         1. 맞다면 dq의 첫 원소와 마지막 원소를 빼내낸다. 
         2. answer의 값을 1 증가시킨다.
      2. dq[0] + dq[-1] > limit이라면, 
         1. dq의 마지막 원소만 pop한다.
         2. answer의 값을 1 증가시킨다. 
   2. dq의 원소의 갯수가 1이라면, 
      1. answer의 값을 1 증가시켜서 리턴한다.
4. answer를 리턴한다. 

결과

후기

탐욕법 문제를 풀고 있는데, 마치 옛날에 창의사고력 수학문제를 푸는 것 같다. 그 말인 즉슨 도통 모르겠다는 뜻이다. 어떤 특별한 방법이나 정해진 유형이 있다기 보다는, 문제를 잘 읽고 이해한 뒤에, 효율적인 방법으로 푸는 것이 중요한 것 같다.