[프로그래머스] LEVEL2 구명 보트 (Python)

문제

문제 링크

문제 해결 접근

[1] 문제의 출제 포인트

• 전형적인 그리디 문제였는데, 내가 그리디처럼 접근하지 못했다.
• 그리디 문제를 접근할 때는 정렬이 같이 사용되는 경우가 많고, 가장 많거나 작은 최적의 해를 찾을 수 있는 조합을 찾아내는 것이 중요하다.
• 당장 눈 앞에서 보이는 부분의 최적의 합이 전체의 최적이 되게끔 문제를 구성하는 것이 중요하다.

[2] 내가 막혔던 부분

• 초반에는 문제를 완전 탐색처럼 접근하려고 했다.
• 예를 들어서, people 리스트를 정렬한 다음에 앞에서부터 순차적으로 탐색하면서 둘을 합칠 수 있으면 합치는 방식으로!
• 그것은 작은 사람들끼리 먼저 합친다는 아이디어였는데, 생각해보면 2명씩 밖에 못태운다는 조건을 생각해보면 틀릴 수밖에 없는 아이디어였다.
• 또한 효율성 테스트도 통과하지 못했는데, 결국 전체를 다 돌면서 확인하고 비교해야 했기 때문이다.

[3] 문제 해결 포인트

• 전형적인 그리디 문제처럼, 가장 큰 것과 가장 작은 것을 합쳐서 태울 수 있으면 태우자! 만약 안 될 경우 큰 사람만 일단 태워버리자!
• 이것을 큐로 구현한다.
  

코드 구현

trial 1 (fail)

def solution(people, limit):
    people = sorted(people) 
    ships = [[0,0] for _ in range(len(people))] ## [현재 중량, 탄 사람의 숫자]
    count = 0

    for idx, p in enumerate(people):
        if idx == 0 : 
            ships[idx] = [p, 1]
            count +=1
            continue
        ## 이전 보트에 함께 타는 경우 
        if (ships[idx-1][0] + p <= limit) and (ships[idx-1][1] == 1):
            ships[idx-1][0] += p 
            ships[idx-1][1] += 1
            continue
        ## 새로운 보트에 타는 경우 
        else:
            ships[idx] = [p, 1]
            count += 1

    return count 

• 반성 포인트 1 : 전혀 그리디처럼 접근하지 못했다.
• 반성 포인트 2 : 심지어 작은 사람들끼리 합치는 알고리즘이기 때문에 틀릴 수밖에 없다.
• 반성 포인트 3 : 내가 문제를 있는 그대로 해석하고, 그대로 적용하여 문자 그대로를 옮기려고 하는 경향이 있는 것 같다...ㅋㅋㅋㅋㅋ

trial 2 (pass!)

from collections import deque

def solution(people, limit):
    people = sorted(people, reverse=True)
    queue = deque(people)
    count = 0
    
    while queue:
        if len(queue)>1 and queue[0] + queue[-1] <= limit: ## 둘을 한 보트에 타게 만든다. 
            queue.popleft()
            queue.pop()
            count += 1
        else:
            queue.popleft() ## 무거운 한 사람만 보트에 타게 만든다. 
            count += 1
    
    
    return count 

• 전형적인 그리디 문제 : 큰 것과 작은 것을 합치는 것이 최적이다라는 개념
• 큐를 사용해서 구현하면 편리하다.