[프로그래머스][LV.2] 구명보트 | python3

문제링크:  구명보트

---

문제설명

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

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

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

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

 

제한조건

- 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
- 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
- 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

---

 

문제풀이

from collections import deque

def solution(people, limit):
    answer = 0
    people.sort()
    people = deque(people)
    
    # 무거운 사람과 가벼운 사람 꺼내기
    # 둘의 무게가 어떠냐에 따라 다음에 꺼낼 수 있는 사람이 다르기 때문에 맨 첨의 값을 밖으로 뺌
    m=people.popleft()
    M=people.pop()
    for _ in range(len(people)):
        if m+M > limit:
            answer+=1
            M=people.pop()
        elif m+M == limit or limit-(M+m) < people[0]:
            answer+=1
            m=people.popleft()
            M=people.pop()
        elif limit-(M+m) >= people[0]:
            m+=people.popleft()
        
            
    return answer

deque로 풀면서

아 한명남았을때 pop을 어떻게 줘야하지.. people에 사람이 안남아있으면 그만해야하는데 그럼 마지막 m과M처리를 못할수도 있는데..그냥 for문 돌려야겠다.. m을 사용하지 못한채로 마지막 루프가 끝나면 어떻게 처리해야하지.. M이나 m 둘 둥 하나 사용했는데 갱신이 안돼서 또 사용하는 경우도 처리해줘야 하는데.. 인덱스에러가 날 코드인데...하는 걸림돌이 머리속을 지나갔지만 어케 해결을 해야할지 감이 안잡혔다. 

1. IndexError 발생 가능성

• people.pop()과 people.popleft()를 여러 번 호출하는데, people이 비어 있는 상태에서 호출하면 IndexError가 발생할 수 있음.
• people.pop()을 할 때 항상 요소가 남아 있다고 보장할 수 없으므로, 빈 리스트일 때 처리를 해야 함.

2. 첫 번째 m, M을 꺼내는 방식의 문제

• m=people.popleft()와 M=people.pop()으로 처음 두 명을 꺼내는데, 이후 루프에서 m과 M을 계속 갱신하면서 진행하는 구조임.
• 하지만 모든 경우에 대해 m과 M을 다시 설정하는 것이 보장되지 않음. 예를 들어, people 리스트에 하나만 남아 있는 경우 M=people.pop()에서 문제가 발생할 수 있음.

3. 불필요한 조건 분기

• elif limit-(M+m) < people[0] 같은 조건이 있는데, 사실상 elif m + M == limit:로 충분할 가능성이 높음.
• elif limit - (M + m) >= people[0]에서 m을 증가시키지만, 이 조건이 필요 이상으로 복잡하게 되어 있음.

4. 탈출 조건 문제

• for _ in range(len(people)):으로 반복문을 돌리는데, people의 길이가 계속 변하기 때문에 예상과 다르게 반복문이 조기 종료되거나 에러가 발생할 가능성이 있음.
• while people:을 사용하는 것이 더 적절함.

---

올바른 해결 방법 

1. IndexError 방지
   • len(people) == 1인 경우를 따로 처리하여 예외 발생을 막음.
   • while people:을 사용하여 리스트 길이에 의존하지 않도록 변경.
2. 불필요한 변수 제거
   • m, M을 별도 변수로 할당하지 않고 people[0]과 people[-1]로 비교하여 처리.
3. 로직 단순화
   • 가장 무거운 사람과 가장 가벼운 사람을 비교하고, 조건에 따라 보트에 태운 후 pop 또는 popleft를 수행하는 방식으로 단순화.

 

그리고 나는 바보였다.. 최대 2명까지만 탈 수 있네... 이걸 못보고 3명 4명이 탈때도 고려함 ㅠㅜ

다시 풀어봐야지

 

내가 푼 풀이로 풀면 마지막에 M을 한 번 썼는데도 갱신이 안돼서 M 값이 계속 들어가는 문제를 해결하지 못함.

미리 빼는 게 아니라 조건을 만족하면 빼는 게 베스트 방법인듯....

 

❌ 미리 빼서 비교하는 방식으로 해결할 수 없는 이유

1. 무거운 사람(M)과 가벼운 사람(m)을 미리 꺼내면, 꺼낸 후 남아 있는 사람들과의 비교가 어렵다.
   • 예를 들어 m + M > limit이면 M을 혼자 태운 후, 다시 people.pop()을 해야 하는데, 이때 m이 다시 처리되지 않음.
   • m이 다음 루프에서 다시 고려되지 않으면, 한 번 더 pop을 수행하면서 보트 개수가 실제보다 많아질 가능성이 있음.
2. 마지막 한 명이 남았을 때 예외 처리하기가 어려움
   • people이 한 명 남았을 때 people.pop()을 하면 IndexError가 발생함.
   • 따라서 while 문을 사용하는 경우, pop() 하기 전에 리스트 길이를 체크하는 구조가 필요함.

나의코드

from collections import deque

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

    while people:
        
        if len(people)==1:
            answer+=1
            break
        if people[0]+people[-1] <= limit:
            people.pop()
            people.popleft()
        else:
            people.pop()
        answer+=1
    return answer

 

---

 

참고하기

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

인덱스로 비교하면 더 간결하다. 시간도 더 효육적인듯

 

 

---

1️⃣ 첫 번째 코드 (deque 사용)

시간 복잡도 분석

1. 정렬 (people.sort()) → O(N log N)
2. while 반복문 (while people:) → O(N)
   • popleft()와 pop() 연산은 각각 **O(1)**이지만, 최악의 경우 N번 수행됨.
   • 따라서 이 부분의 복잡도는 O(N).

➡️ 총 시간 복잡도:
O(N log N) + O(N) = O(N log N)

---

2️⃣ 두 번째 코드 (투 포인터 사용)

시간 복잡도 분석

1. 정렬 (people.sort()) → O(N log N)
2. while 반복문 (while a < b:) → O(N)
   • a와 b가 한 번씩 이동하며 리스트를 순회하는 방식.
   • 따라서 이 부분의 복잡도는 O(N).

➡️ 총 시간 복잡도:
O(N log N) + O(N) = O(N log N)

---

📌 결론: 두 코드의 시간 복잡도는 동일 (O(N log N))

하지만 두 번째 코드(투 포인터 방식)가 더 효율적이다.

왜 더 효율적인가?

1. deque를 사용하지 않음
   • deque.popleft()는 **O(1)**이지만, deque 자체를 만들고 관리하는 오버헤드가 있음.
   • 반면, 두 번째 코드는 리스트의 인덱스를 사용하여 직접 접근하므로 더 가볍고 빠름.
2. 더 적은 연산 수행
   • 첫 번째 코드에서는 popleft()와 pop()을 수행하여 데이터 구조를 변경하지만,
   • 두 번째 코드는 단순히 리스트의 인덱스를 조작하는 방식이므로 연산량이 적음.

💡 즉, 두 코드의 이론적인 시간 복잡도는 같지만, 실질적인 실행 속도에서는 두 번째 코드(투 포인터)가 더 빠름. 

 

---

 

📌 1. 투 포인터(Two Pointer) 알고리즘

• 배열의 양쪽 끝에서 시작하는 두 개의 포인터(a와 b)를 조작하며 문제를 해결하는 기법.
• 정렬된 리스트에서 유용하게 쓰이며, 한 번의 탐색(O(N))으로 원하는 결과를 찾을 수 있도록 최적화함.

🛠 투 포인터를 활용하는 이유

• 정렬된 리스트에서 특정 조건(무게 합이 제한을 넘지 않음)을 만족하는 두 개의 요소를 빠르게 찾을 수 있음.
• 하나씩 비교하면서 이동하는 방식이므로 불필요한 연산을 줄여 효율성을 극대화.

---

📌 2. 그리디(Greedy) 알고리즘

• 각 단계에서 가장 최적의 선택(현재 가벼운 사람과 무거운 사람을 함께 태우는 것)을 하면서 전체 최적 해를 찾는 방법.
• 이 문제에서는 가장 무거운 사람(b)과 가장 가벼운 사람(a)을 조합하면서 최대한 많은 사람을 한 번에 태워 보트 개수를 최소화함.

🛠 그리디를 활용하는 이유

• 현재 최선의 선택(가장 무거운 사람을 최대한 가벼운 사람과 함께 태우는 것)이 전체적으로도 최선의 결과를 보장하기 때문.
• "보트 개수를 최소화"하는 목표를 달성하기 위해 현재 가능한 가장 가벼운 사람과 무거운 사람을 함께 보내는 것이 최적의 선택이므로 그리디 알고리즘이 적합함.

---

📌 결론: "투 포인터 + 그리디" 알고리즘

🚀 핵심 아이디어

1. 사람들의 몸무게를 오름차순 정렬한다. (O(N log N))
2. 가장 가벼운 사람(a)과 가장 무거운 사람(b)을 비교하면서 보트에 태운다. (O(N))
3. 둘이 함께 탈 수 있으면 a를 증가시켜서 다음 가벼운 사람을 고려하고,
   함께 탈 수 없으면 b만 감소시키면서 혼자 태운다.
4. 모든 사람이 탈 때까지 반복하며, 보트 개수를 계산한다.

👉 시간 복잡도: O(N log N) (정렬) + O(N) (투 포인터 탐색) = O(N log N)
👉 공간 복잡도: O(1) (추가 공간 없음, 리스트 인덱스만 사용)