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

📃 문제:

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

프로그래머스

 

✏️ 나의 풀이

- 순차적으로 탐색해서 조건에 맞는지 확인한다면, 다음과 같은 반례가 있음

[50, 50, 30, 20, 70, 80], limit = 100 -> 50+50, 30+20, 70, 80 으로 4개의 구명보트가 필요하지만, 20+80, 30+70, 50+50으로 태우면 3개의 구명보트만 필요하다. 

- 그래서 가장 몸무게가 많이 나가는 사람과 적게 나가는 사람을 쌍을 이뤄 최대한 태우는 것이 가장 최소를 보장한다.

 

❌ 효율성 틀린 풀이

- 오름차순으로 people리스트를 정렬하고, 우선순위 큐를 이용해서 항상 최솟값을 반환해서 두 값을 더했을 때 limit가 넘는지 확인하는 알고리즘을 생각했다. limit가 넘지 않는다면 최솟값을 다시 한번 반환해서 또 확인하는 구조로 로직을 짰었는데, 정확성은 맞았는데 효율성에서 0점이 나왔다.

- 이 풀이도 나름 시간이 걸렸던 포인트를 적으면

1. 최대 값 + 최소값 <= limit 일 때, 다음 최소값도 더했을 때 limit이 넘지 않는지 확인하는 것 -> 넘는다면 다시 우선순위 큐에 넣어준다. 
2. 최대 값과 최소값을 각각 다른 변수에 할당했지만, 결국 같은 사람을 확인하므로 구명보트에 태운 사람인지 확인하는 것 -> 리스트의 인덱스로 확인하도록 했다.

 

무인도에 갇힌 사람은 최대 50,000명이라서 효율성 괜찮을줄 알았는데..!!

import heapq
import copy 

def solution(people, limit):
    answer = 0
    count = 0
    check = [0] * len(people)
    idx_people = [(people[i], -i) for i in range(len(people))]
    ascend_people = sorted(idx_people, reverse = True)
    heapq.heapify(idx_people)
    
    for v, i in ascend_people:
        i = abs(i)
        if not check[i]:
            while idx_people:
                min_v, min_idx = heapq.heappop(idx_people)
                min_idx = abs(min_idx)
                if i==min_idx:
                    pass

                if not check[min_idx]:
                    if v + min_v <= limit:
                        check[min_idx] = 1
                        check[i] = 1
                        answer += 1
                        break
                    else:
                        heapq.heappush(idx_people, (min_v, -min_idx))
                        check[i] = 1
                        answer += 1
                        break

    return answer

 

✅ 정답 풀이

- 투 포인터를 활용해서 풀면 정말 간단하다.
- 사람을 추가했을 때 limit가 넘는다면 바로 하나의 구명보트를 배정해야되기 때문에 right 포인터는 계속 이동한다.

def solution(people, limit):
    answer = 0
    people.sort()
    l = 0
    r = len(people) - 1
    
    while l<=r:
        if people[l] + people[r] <= limit:
            l+=1
            r-=1
            answer += 1
        else:
            r-=1
            answer +=1
        if r<0:
            break
    
    

    return answer

 

하나의 기준값을 고정할 수 있다면 투포인터 방식도 고려해보자