[Python] 프로그래머스, 구명보트 Lv.2 (feat.sort와 sorted, deque, 투포인터, 시간초과, 파이썬)

반짝반짝 알고리즘, 인프준

 

 

 

구명보트

문제 링크

프로그래머스

 

 

문제 설명

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

 

 

 

 

 

해결 과정

제한사항을 보면 구명보트의 무게 제한은 사람들의 몸무게 중 최댓값보다 크게 주어진다고 합니다. 그러므로 사람들을 구출할 수 없는 경우는 없습니다. 그렇기 때문에 people에 담긴 값은 모두 제거될 수 있으므로 people값이 없을 때까지 while문 구현이 가능합니다.

 

1. 필요한 구명보트의 개수 count를 선언해 주고 people을 몸무게 오름차순으로 정렬해 줍니다.

 

2. 사람들을 1명 혹은 2명씩 구출할 것이기 때문에 다 구출될 때까지 while문을 돌리고 그때마다 count를 1씩 더해 구명보트의 개수를 세어줍니다.

 

3. pop함수를 통해 몸무게가 가장 무거운 사람을 구출해 줍니다.

 

4. 가장 무거운 사람을 구출할 때 가장 가벼운 사람이 같이 타도 무게 제한에 걸리지 않는다면 같이 구출하고, 가벼운 사람도 remove 함수를 통해 people에서 제거해 줍니다.

 

5. 이렇게 사용한 구명보트의 개수를 반환해 줍니다.

 

 

pop과 remove

def solution(people, limit):
    count = 0       # 구명보트 개수
    people.sort()   # 오름차순, 사람들의 몸무게 기준
    
    # 모든 사람이 구출될 때 까지
    while people:
        # 몸무게가 가장 큰 사람 구출
        person = people.pop()
        # 아직 남은사람이 있고, 가장 가벼운 사람이 무거운 사람과 같이타도 무게 제한에 안걸리면 같이 구출
        if len(people) > 0 and person + people[0] <= limit:
            people.remove(people[0])
            
        count += 1
    
    return count

 

 

효율성 테스트, 시간 초과

 

위 코드는 논리에 문제가 없기에 대부분의 테스트 케이스에서 성공하지만 한 가지 효율성 테스트에서 시간초과가 발생하게 됩니다. pop으로 몸무게가 무거운 사람을 구출하는데 문제없지만 remove로 특정 인덱스를 제거하면서 시간 복잡도가 높아짐에 따라 시간 초과가 발생한 것 같습니다. pop과 같이 맨 앞의 값을 제거하는 함수가 필요해졌습니다.

 

💡 liist의 pop()과 remove()의 시간복잡도는 O(1)이고, pop(0)과 remove(0)의 시간복잡도는 O(n)이다.

 

 

 

pop과 popleft

 

remove(index)로 인해 시간 복잡도가 높아져 시간 초과가 발생하므로 remove 대신 맨 앞에 사람을 구출할 수 있는 popleft 함수를 사용하기 위해 Queue로 접근했습니다. 위 코드에서 2가지 사항만 변경했습니다.

 

 

1. list의 remove 함수 대신에 deque의 popleft 사용하여 가벼운 사람을 구출한 점

💡 List
pop([i]) - 인덱스 i에 있는 항목을 제거하고 이를 반환, 기본값은 -1이므로 마지막 항목이 제거되고 반환
remove(x) - 첫 번째 x를 제거합니다.

💡 Queue
pop() - 데크의 오른쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, IndexError를 발생시킵니다.
popleft() - 데크의 왼쪽에서 요소를 제거하고 반환합니다. 요소가 없으면, IndexError를 발생시킵니다.

 

2. deque에 바로 담아주기 위해 sort 함수를 sorted 함수로 변경해 준 점

some_list = [ 2, 3, 1 ]

''' sort - some_list 자체를 정렬함. '''

# 1. 정렬 후 바로 출력
print(some_list.sort()) # None

# 2. 정렬이 완료된 후 출력
some_list.sort()
print(some_list) # [ 1, 2, 3 ]

# 3. 내림차순 정렬
some_list.sort(reverse=True)
print(some_list) # [ 3, 2, 1 ]


''' sorted - some_list에 영향을 주지않고 새로운 리스트를 반환함. '''

# 1. 정렬 후 바로 출력
print(sorted(some_list)) # [ 1, 2, 3]

# 2. 새로운 리스트를 만들어 출력
some_list2 = sorted(some_list)
print(some_list2) # [ 1, 2, 3 ]

# 3. 내림차순 정렬
some_list3 = sorted(some_list, reverse=True)
print(some_list3) # [ 3, 2, 1 ]

 

 

제출 코드

from collections import deque
def solution(people, limit):
    count = 0                      # 구명보트 개수
    people = deque(sorted(people)) # 오름차순, 사람들의 몸무게 기준
    
    # 모든 사람이 구출될 때 까지
    while people:
        # 몸무게가 가장 큰 사람 구출
        person = people.pop()
        # 아직 남은사람이 있고, 가장 가벼운 사람이 무거운 사람과 같이타도 무게 제한에 안걸리면 같이 구출
        if len(people) > 0 and person + people[0] <= limit:
            people.popleft()
            
        count += 1
    
    return count

 

 

 

 

파이썬의 자료구조와 시간복잡도에 대한 이해가 중요했던 문제였습니다. 시스템의 규모와 시간복잡도의 중요성은 비례합니다. 아래 시간복잡도에 대해 쉽게 정리한 글을 같이 첨부합니다.

 

 

빅오 표기법:Big-O Notation 정의/특징/복잡도/종류/비교/예제

 

 

 

 

또 다른 풀이

 

def solution(people, limit) :
    answer = 0
    people.sort()

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer

 

 

deque를 사용하지 않고 투 포인터 알고리즘을 써서 시간복잡도를 줄인 코드입니다. 기본적인 탐색(반복문)을 써서 시간 초과가 발생하는 경우 투 포인터 알고리즘을 사용하면 메모리와 시간 효율성을 높일 수 있습니다.

 

 

💡 Two Pointers - 두 가지의 포인터를 사용하여 문자열 또는 배열에서 원하는 값을 찾거나 반복할 때 쓰는 알고리즘의 종류

 

 

 

 

 

 

 

---

 

 

 

 

 

 

 

출처: 프로그래머스 코딩 테스트 연습,https://school.programmers.co.kr/learn/challenges