[programmers] Greedy - 구명보트

문제

programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트

 

풀이

해당 문제도 풀이 과정 자체는 떠올리기가 쉬운 편이다. 하지만 속도를 최적화하는 과정에서 오래 걸린 문제였다.

조건을 생각해 보면, 2명까지만 탑승이 가능하고, 가능한 한 적은 숫자의 보트를 보내는 것이 목표이다. 따라서 무게를 최대한 한계에 맞춰서 태워 보내는 것이 중요하다.

그래서 해당 조건을 만족하기 위해 필연적으로 탐색을 진행해야 한다. 하지만 이 탐색 과정에서, 연산을 최소한으로 사용하는 것이 목표이다.

필자는 다음과 같은 방식으로 그리디 알고리즘을 적용했다.

1. 사람을 무게 오름차순으로 배열한다.
2. 사람 배열을 순환하면서 자기 자신과 바로 앞 위치의 값을 더하면 한계보다 클 경우, 바로 멈춘다.
3. 그게 아닐 경우, rightidx라는 값을 이용한다. 이를 통해 뒤쪽 가장 큰 값부터 차례대로 자기 자신의 값과 더해서 한계보다 크지 않을 경우, 뒤쪽의 값을 리스트에서 빼내고, 이후의 반복은 빼낸 값 바로 앞의 값부터 다시 앞쪽으로 쭉 반복한다.

3번과 같이 반복하는 이유는, 소팅을 진행했기 때문에 맨 앞에는 가장 작은 값, 맨 뒤에는 가장 큰 값이 배치되게 된다. 첫번째 순환을 생각해 보자, 이때 맨 앞의 값과 맨 뒤의 값부터 차례로 앞쪽으로 가면서 비교하게 되는데, 두개의 합이 한계보다 큰 경우 그 다음 값으로 넘어가는 식으로 순환이 진행된다. 그러다 합이 한계값보다 크지 않을 경우, 해당 값을 빼낸 뒤 그 다음 순환에서는 앞쪽은 두번째 값, 뒤쪽은 빼낸 값의 바로 앞쪽 값부터 음의 방향으로 비교한다. 왜냐하면 첫번째 값보다 두번째 값이 무조건 크거나 같기 때문에, 빼낸 값보다 양의 방향에 있는 값은 굳이 비교할 필요도 없이 한계값보다 커지기 때문이다. 이러한 방식으로 앞쪽, 뒤쪽으로 포인터를 사용하였고, 이 역시 투포인터를 사용하여 값을 구하는 편이 pop연산을 사용하는 것보다 속도가 빠르지만, pop연산을 사용해서 코드가 간결해졌고, 문제가 해결되었기 때문에 이 방식을 사용하였다.

마지막에 전체에 대한 순환이 끝나면 전체 리스트의 길이를 구하는 것으로 답안을 구해주면 된다.

 

코드

def solution(people, limit):
    people.sort()
    rightidx = len(people)
    
    for i in range(len(people)):
        if people[i] + people[i+1] > limit:
            break
            
        while True:
            rightidx -= 1
            
            if people[i] + people[rightidx] <= limit:
                people.pop(rightidx)
                break
                
    answer = len(people)
    
    return answer