deque를 사용해야할때는?

1. 문제

 

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

코딩테스트 연습 - 구명보트

 

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

 

예를 들어 사람들의 몸무게가 [70,50,80,50]이고 구명보트의 무게 제한이 100kg이면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

 

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

 

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 구명보트 개수의 최솟값을 return하도록 solution함수를 완성하세요

 

2. 제한사항

 

무인도에 갇힌 사람은 1명 이상 50000명 이하

 

각 사람의 몸무게는 40kg이상 240kg이하

 

구명보트의 무게 제한은 40kg이상 240kg이하

 

구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

3. 입출력 예시

 

그림1. 입출력 예시

 

4. 나의 풀이

 

문제의 핵심은 주어진 몸무게 리스트에서 최대 몸무게인 사람과 더 태울수 있으면 최소 몸무게인 사람을 먼저 태워야함

 

리스트에서 pop을 해버리면 O(n)이라 시간을 많이 소요한다고함. 그래서 옳게 짜도 효율성 테스트를 통과하지 못함

 

deque로 만들어서 pop을 하면 O(1)이라 효율적임

 

def solution(people, limit):
    answer = 0
    
    from collections import deque
    
    people.sort()
    
    deque_people = deque(people)
    
    len_people = len(people)
    
    while len_people > 1:
        
        if limit >= deque_people[0] + deque_people[-1]:
            deque_people.pop()
            deque_people.popleft()
            answer += 1
            len_people -= 2
        
        else:
            deque_people.pop()
            answer += 1
            len_people -= 1
    
    #if len_people == 1:
        #answer += 1
        
    return answer + len_people

 

people을 sort해서 최소부터 최대로 정렬하고 deque로 만든다음에 people의 길이를 미리 구해놓는다

 

길이를 미리 구하는 이유는 반복문에서 len()함수를 계속 사용하여 시간낭비를 하는 것을 방지함

 

def solution(people, limit):
    answer = 0
    
    from collections import deque
    
    people.sort()
    
    deque_people = deque(people)
    
    len_people = len(people)

 

while로 반복문을 수행하는데 위에서 언급한대로 최대 몸무게를 가진 사람 -1번 index와 최소 몸무게를 가진 사람 0번 index의 합이 limit를 넘는지 안넘는지를 비교함

 

만약 넘지 않으면 최대 몸무게 사람과 최소 몸무게 사람을 제거하고 구명보트 하나 썼으니 answer에 1을 더하고 사람이 두명 줄었으니 len_people은 2를 빼줌

 

만약 최대 몸무게 사람과 최소 몸무게 사람의 합이 limit를 넘으면 최대 몸무게 사람만 제거하도록 deque.pop()을 사용함

 

1명만 빠졌으니 len_people은 1을 빼고 구명보트 하나 쓴거니까 answer에 1을 더해줘

 

    while len_people > 1:
        
        if limit >= deque_people[0] + deque_people[-1]:
            deque_people.pop()
            deque_people.popleft()
            answer += 1
            len_people -= 2
        
        else:
            deque_people.pop()
            answer += 1
            len_people -= 1

 

이제 people이 점점 줄어들면서… len_people=1이 되었다고 쳐봐… 그러면 이 1명은 어차피 무조건 태울수 있으니까 while문을 탈출할거임

 

len_people=2에서는 반복문을 수행하는게 좋다. 2명을 다 태울수 있거나 1명만 태울 수 있거나 2명 태워서 len_people=0이 되어도 반복문 탈출하면 돼

 

아무튼 len_people이 1이거나 0이 되었을때 이제 반복문을 탈출할건데 len_people=1이면 구명보트 하나 써서 태워야하니까 answer에 1을 더해줘야겠지

 

len_people은 0이면 태울사람 없으니 바로 answer를 return하면 돼

 

근데 이제 여기서 if문을 써버리면 그만큼 시간이 소요될거라서… 이게 어차피 len_people=1이면 1을 더할거고 0이면 0을 더할거니까 최종 return값에 len_people을 더하는걸로 시간을 조금이라도 줄일 수 있지 않을까?

 

    #if len_people == 1:
        #answer += 1
        
    return answer + len_people

 

5. 다른 풀이-1

 

리스트에서 pop이 O(n)이라 안쓰고 풀 수 있어야하는데 

 

deque의 pop을 안쓰고 index 이동만으로도 풀어낸 풀이가 있다

 

알고리즘 핵심은 나랑 동일한게 최대 몸무게 사람과 최소 몸무게 사람을 먼저 태우기

 

근데 조금 다른 점이 모든 people에 boat를 1개씩 줄거고 매 순간마다 최소 몸무게를 가진 사람은 최대 몸무게를 가진 사람과 같이 탈수 있으면 같이 태우고 최소 몸무게를 가진 사람이 가진 보트는 버릴거임

 

def solution(people, limit):
    dump = 0
    
    people.sort()
    
    total_boat = len(people)

    a = 0
    b = total_boat - 1
    
    while a < b :
        
        if people[b] + people[a] <= limit :
            a += 1
            dump += 1
            
        b -= 1
        
    return total_boat - dump

 

일단 people 모두에 보트 1개씩을 준다고 생각을 하셈. total_boat = len(people)개 만큼 보트 1개씩을 쓸건데

 

먼저 people을 sort해서 최소 몸무게부터 최대 몸무게로 정렬하고

 

초기 index를 a=0으로 최솟값 가리키고 b=total_boat-1로 최댓값을 가리키도록

 

def solution(people, limit):
    dump = 0
    
    people.sort()
    
    total_boat = len(people)

    a = 0
    b = total_boat - 1

 

people 리스트에서 최솟값과 최댓값을 indexing만으로 추출해서 limit와 비교를 할거임

 

만약 limit를 넘지 않으면 a에 1을 더해주면서 최솟값 사람을 현재 최댓값인 b가 가리키는 보트에 태울거고 a-1이 가리킨 보트는 버리겠다는 의미로 dump에 1을 더해줌

 

매 순간 최대 몸무게를 가진 사람은 boat에 타니까 b에는 항상 1을 빼줘서 이동을 시킬거임

 

    while a < b :
        
        if people[b] + people[a] <= limit :
            a += 1
            dump += 1
            
        b -= 1

 

while문으로 반복하는 동안 최댓값이 가리키는 index는 왼쪽으로 계속 이동을 할건데 a<b일때만 반복을 할거임

 

반복을 탈출하면… 생각을 해보자.. 마지막 리스트에 2명만 남았을때…

 

2명을 모두 태울 수 있다면 a값은 1 더해지고 b값은 1 감소해서 a>b가 될거거든

 

혹은 최대 몸무게 b가 가리키는 사람만 탄다면 a는 그대로고 b는 1 감소해서 a=b가 될거거든

 

그러면 a=b일때는 결국 1명이 남는다는 소리

 

어떻게 되든 dump랑은 상관없으니까 이제 total_boat에서 버릴 보트 dump를 빼주면 정답 추출

 

6. 다른 풀이-2

 

근데 이게 이해하기 어려워서 직관적으로 나 같이 할려면

 

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
            
        b -= 1
        answer += 1
    
    if a == b:
        answer += 1
        
    return answer

 

위와 같이 최솟값과 최댓값을 합해서 limit를 넘지 않으면 최솟값 사람 태운다는 의미로 index a에 1을 더해서 최소가 가리키는 부분을 오른쪽으로 1칸 옮기고

 

매 순간마다 최댓값 사람은 항상 태울거니까 b에는 1을 빼서 왼쪽으로 계속 이동시킬거고

 

매 순간마다 answer에는 1을 더해서 보트를 쓸거거든

 

if people[b]+people[a]<=limit 문을 수행하면 2명을 태우는거고 수행하지 않으면 1명만 태우는거임

 

그리고 while을 나왔을때 a=b이면 1명 남은거고 a>b이면 0명남은거라서 a=b일때 answer에 1을 더해줌

 

7.되돌아보기

 

탐욕법 알고리즘으로 주어진 몸무게 리스트에서 최대 몸무게인 사람과 더 태울수 있으면 최소 몸무게인 사람을 먼저 태워야 최소로 boat를 쓴다는 것을 이해해야함

 

이 문제로 기억해야할 것은 pop에 대해서인데 

 

일반 리스트에서 list.pop()을 하면 O(n)인데 deque로 만들어서 pop을 하면 O(1)이어서 효율이 좋다는 것을 기억해야한다

 

나의 풀이에서 마지막 if문을 안쓰고도 return할 수 있는 섬세함이 필요

 

다른 풀이에서 pop을 쓰지 않고도 리스트의 원소를 제거하는 방법으로 index 이동으로도 풀 수 있다는걸 꼭 기억해두자