[프로그래머스] 구명보트 (Level 2) (파이썬 python)

 

 

 

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=python3

프로그래머스

 

 

문제 풀이

 

def solution(people, limit):
    answer = 0
    people.sort()
    start, end = 0, len(people) - 1
    while start < end:
        answer += 1
        if people[start] + people[end] <= limit:
            start += 1
            end -= 1
        else:
            end -= 1
    if start == end: answer += 1
    return answer

 

투 포인터를 활용해서 문제를 풀이할 수 있다!

투 포인터 기법은 맨 앞과 맨 뒤에서부터 두 개의 포인터를 가지고 이동하며

모든 원소를 탐색하는 기법이다.

 

이에 따라 start, end 변수에 0, 최대 인덱스를 넣어준다.

그리고 중간에서 두 포인터가 만날 때까지 반복을 해주는 것이다.

 

이 문제의 포인트는 무게 순으로 오름차순 정렬을 진행하여

1. 맨 앞 인덱스 + 맨 뒤 인덱스의 무게 합이 limit보다 작을 경우

두 사람을 모두 옮긴다는 뜻으로 포인터를 각각 오른쪽, 왼쪽으로 이동해준다.

2. 맨 앞 인덱스 + 맨 뒤 인덱스의 무게 합이 limit보다 클 경우

가장 무거운 사람만 옮겨준다

(이 사람은 현재 기준 가장 가벼운 사람과도 함께 옮길 수 없으니 무조건 혼자 가야한다)

 

이 두 경우로 무조건 한 명 이상씩 옮겨준다.

(= 무조건 while문이 한 번 돌아갈 때마다 구명보트가 하나 사용되므로 answer은 1씩 커진다)

 

 

딱 맞게 마지막 2명이 함께 타며 모든 사람에 대한 탐색이 끝날 수도 있지만,

두 번재 테스트케이스인

[70, 80, 50] 에서는 경우가 다르다

한 명씩만 이동할 수 있기 때문에 80, 70이 먼저 빠진 뒤

50kg 사람만 한 명 남고 start와 end 인덱스가 동일해진다.

이런 상황에서는 마지막 한 명까지 이동시켜줘야하므로 정답에 1을 추가해줘야한다.

 

 

느낀 점

 

그리디 문제를 많이 안풀어본 것 같아 도전해봤는데

잊고 있던 투 포인터 개념이 직관적으로 보이는 좋은 문제였던 것 같다!