programmers.co.kr 코딩테스트 연습 > 탐욕법(Greedy) > 구명보트

 

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42885

보트에는 최대 2명까지 탈 수 있습니다.

2명의 몸무게의 합이 limit 보다 작다면, 몸무게가 작은사람 + 몸무게가 큰 사람

이렇게 짝을 지어서 보트에 태워야, 보트의 수를 최소화 할 수 있습니다.

몸무게가 가장 작은 사람을 찾기 위해서, 사람들의 몸무게를 정렬 합니다.

(limit - 첫번째 사람의 몸무게) 보다 작지만, 이 보다 작은 사람들 중에서는

가장 큰 몸무게를 가진 사람을 찾아야 합니다.

그러면 제일 오른쪽 사람 부터 왼쪽 방향으로 확인합니다.

이 때, (limit - 첫번째 사람의 몸무게) 몸무게 보다 큰 사람은,
같이 탈 수 있는 작은 몸무게를 가진 사람이 없기 때문에, 혼자서 보트를 타야 합니다.

몸무게가 작은 사람을 가리키고 있는 idx_left 와,

몸무게가 큰 사람을 가리키고 있는 idx_right 2개의 인덱스가 있습니다.

 

from typing import List

def solution(people: List, limit: int):
    people.sort()
    answer = 0
    idx_left, idx_right = 0, len(people) -1

 

2개의 인덱스는 배열의 시작과 끝을 가리키는 초기값을 가집니다.

from typing import List

def solution(people: List, limit: int):
    people.sort()
    answer = 0
    idx_left, idx_right = 0, len(people) -1

    while idx_left < idx_right:
        if people[idx_right] > limit - people[idx_left]:
            idx_right -= 1
            answer += 1
        else:
            idx_left += 1
            idx_right -= 1
            answer += 1

    if idx_left == idx_right:
        answer += 1

    return answer

이 방식으로 문제를 풀면 O(n) 으로 문제를 풀 수 있습니다.

같은 O(n)이지만, 리스트에서 몸무게가 적은 사람, 또는 많은 사람을 빼는 방식으로

pop(0) 또는 pop()을 사용해서 문제를 풀수도 있습니다.

하지만, 인덱스를 이동하는 방식보다, pop() 조금 느리기 때문에,

테스트 케이스를 조금 스포하자면, 이 문제의 효율성 테스트 1번을 통과 하는 것이 쉽지 않습니다. 

 

따라서 실행속도가 최대한 빠르게 구현을 하기 위해서, 리스트의 pop()메서드를 사용하기 보다는

배열의 index를 옮기는 방식으로 구현 해야 합니다.