99클럽 코테 스터디 19일차 TIL (구명보트 - 프로그래머스)

 

오늘의 학습 키워드:  Greedy, deque

문제: 구명보트

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

프로그래머스

풀이

풀다 보니 효율성 테스트에서 조금 오래 걸린 문제입니다. 아이디어를 도중에 변경하여 해결했습니다.

 

구명보트에 사람을 태워보낼때 작은 무게의 사람부터 태워 보내자니 최적의 조합을 찾는데
시간이 오래 걸리는 문제가 발생했습니다.

가장 작은 한사람을 태우고 보트의 제한까지 가장 큰 무게의 사람을 태워야 하기 때문입니다.

 

따라서 발상의 전환으로 가장 큰 무게의 사람부터 태워보냈습니다. 무게가 남는 경우에는 가장 몸무게가 작은 한 사람만 비교하면 되기 때문에 시간적으로 무리 없이 진행가능합니다.

 

deque를 사용해서 진행하였습니다.

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort()
    q = deque(people)
    
    while q:
        f = q.popleft()
        try:
            b = q.pop()
            answer+=1
            if f+b > limit:
                q.appendleft(f)
        except:
            answer+=1
    
    return answer

 

회고

다각도로 문제를 뜯어보는 과정이 필요할것 같습니다. 실전이라면 바로 틀렸을 것 같습니다.

내일 학습할 것.

SQL, Python, 독서