[Python 파이썬] 프로그래머스 - 구명보트

2024년 6월 11일

문제 링크 : 프로그래머스 - 구명보트

프로그래머스

 

 

---

문제 접근

 

문제에서 주어진 조건들 중, 가장 중요한 정보는 다음과 같다.

 

1. 구명보트는 한 번에 최대 2명만 탈 수 있다.

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

 

 

limit가 100인데, 사람의 몸무게가 120인 경우는 없다는 뜻이다. 이러면 고려해야 할 사항이 줄어들어 생각하기 편하다.

 

그리디하게 접근해, 최대한 많은 사람을 태우려면 가장 무거운 사람 + 가장 가벼운 사람을 묶어서 태울 수 있는지 확인해야 한다.

 

이에 착안하여 두 포인터를 활용해 핵심 로직의 시간복잡도를 O(N)으로 로직을 구성해보기로 했다.

 

 

 

구명보트의 한계 무게는 100, 사람들의 무게는 위와 같이 주어졌다고 가정해보자.

 

가장 가벼운 사람과 가장 무거운 사람을 한 쌍으로 묶어보기 위해선 정렬을 해주어야 한다.

 

 

정렬하면 위와 같고, cnt는 필요한 구명보트 수이다.

 

가장 가벼운 사람은 가장 왼쪽 인덱스이고, 가장 무거운 사람은 가장 오른쪽 인덱스일 것이다.

끝점에 각각 left, right 위치를 지정해준다.

 

 

 

이제부터 우리는, 둘이 같이 탈 수 있다면 양 포인터를 가운데로 한 칸씩 당기고, 만약 둘이 같이 못 탄다면 무거운 사람만 태우기 위해 right만 가운데로 한 칸 땡길 것이다.

 

left와 right를 더해보니, limit를 넘어가는 110이 된다. 둘은 같이 못타므로, 무거운 사람만 태우기 위해 right를 가운데로 한 칸 이동시키고 cnt를 1 증가시킨다.

 

 

 

left와 right를 비교해보니, limit와 동일하기에 둘은 같이 탈 수 있다.

두 포인터를 가운데로 한 칸씩 이동시키고 cnt를 1 증가시킨다.

 

 

이러한 과정을 left가 right 위치와 같거나 그 너머로 넘어갈 때까지 반복한다.

 

로직을 수행하다보니 left와 right가 같아졌다. 같은 사람을 가리키므로 left와 right가 같을 때에는 cnt를 1 증가시키고 로직을 종료하게 된다.

 

left와 right가 같을 때, 같은 사람의 몸무게를 두 번 더해서 로직의 오류가 생기지 않을까 싶었는데, 어느 경우에도 하나의 보트를 더 필요로 하는 것은 똑같아서, 조건문을 추가로 걸어두지 않았다.

 

# 고려했다가 삭제했던 조건문
# left, right가 같은 곳 가르킬 수 있음.
if left == right:
    answer += 1
    break

 

 

---

전체 코드

 

def solution(people,limit):
    answer = 0

    people.sort()
    left = 0
    right = len(people) - 1

    while left <= right:
        if people[left] + people[right] <= limit:
            answer += 1
            left += 1
            right -= 1
        else:
            answer += 1
            right -= 1

    return answer

if __name__ == "__main__":
    people = [50, 40, 20, 80, 50, 70, 90]
    limit = 100

    print(solution(people, limit))

---

풀이 후기

 

그리디하게 접근가능한 간단한 문제 중 하나였다.

무거운 사람에게 최대한 가벼운 사람을 붙여줄 수 있을 만큼 붙여주는 접근 방법을 떠올린다면 어렵지 않게 구현 가능하다고 생각한다.