Jin의 일상

문제

1. 구명보트에 탈 사람들의 몸무게가 리스트(people)로 주어진다. 

2. 구명보트는 최대 2명이 탑승할 수 있다. (단, 구명보트의 최대 탑승 무게(limit) 보다 적어야 한다.)

3. 모든 사람들이 구명보트를 통해 탈출해야 한다.

4. 항상 사람의 무게는 구명보트의 최대 무게보다 작다.

문제 특징

1. 효율성 테스트가 상당히 엄격했다. 반드시 1개의 반복문을 통해서만 코드를 작성해야 한다.

2. people이 [30, 40, 60, 70]인 반례 상황이 존재한다. 

[30+40, 60, 70]으로 배를 탈 수도 있지만, [30+70, 40+60]으로 배를 탈 수도 있다. 후자가 문제에서 요구하는 정답이다.

알고리즘

- people을 정렬시킨다. 

- 리스트(people)의 맨 앞에서 뒤쪽으로 이동하는 변수를 만든다(front)

- 리스트(people)의 맨 뒤에서 앞쪽으로 이동하는 변수를 만든다(back)

- 반복문에서 back은 항상 왼쪽으로 한 칸씩 움직인다.

- people의 front 번째 값과 back번 째 값을 더해서 limit보다 작거나 같다면 front를 한 칸 오른쪽으로 이동시킨다.

- front보다 back이 작아질 때까지 진행한다.

1번 테스트 케이스

people = [70, 50, 80]

limit =  100

1. people을 정렬시킨다.

[70, 50, 80] -> [50, 70, 80]

2. 

- back과 front를 더하면 limit인 100보다 크므로 front는 가만히 있는다.

- back을 왼쪽으로 한 칸 움직이자

3.

- back과 front를 더하면 limit인 100보다 크므로 front는 가만히 있는다.

- back을 왼쪽으로 한 칸 움직이자.

- back과 front를 더하면 limit인 100보다 크므로 front는 가만히 있는다.

- back을 왼쪽으로 한 칸 움직이자. (back을 왼쪽으로 움직이면 front보다 앞에 위치하므로, 반복문을 종료한다.)

2번 테스트 케이스

people = [30, 40, 50, 60]

limit =  100

1. people 정렬한다. [30, 40, 50, 60] -> [30, 40, 50, 60]

2.

- back과 front를 더하면 limit인 100보다 작으므로 front도 오른쪽으로 한 칸 움직이자.

- back을 왼쪽으로 한 칸 움직이자. 

3.

- back과 front를 더하면 limit인 100보다 작으므로 front도 오른쪽으로 한 칸 움직이자.

- back을 왼쪽으로 한 칸 움직이자. (back이 front보다 앞으로 가게 되므로 반복문이 종료된다.)

코드

def solution(people, limit):
    answer = 0
    people = sorted(people)
    front = 0
    back = len(people)-1
    while front < back:
        answer += 1
        if people[front] + people[back] <= limit:
            front += 1
        back -= 1
    return answer