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

 

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

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

 

문제설명: people로 주어지는 배열에 사람들의 몸무게가 주어지고, limit 변수로 구명보트의 제한 무게가 주어진다.

구명보트 1개는 한 번에 최대 2명씩 태울 수 있으므로 모든 사람을 구출하기 위해 필요한 구명보트의 최소개수를 구하는 문제이다.

 

 

[1차 시도]

def solution(people, limit):
    ans = 0
    people.sort(reverse=True)
    start = len(people)-1
    for i in range(len(people)):
        if i==start:
            ans+=1
            break
        for j in range(start,i,-1):
            ans+=1
            if people[i]+people[j] <= limit:
                start-=1
            break
    return ans

 

풀이: 몸무게를 순서대로 정렬하여 무거운 사람부터 태우면서 구명보트 제한 몸무게가 넘지 않는다면,

가벼운 사람을 한명씩 추가해서 구명보트의 개수를 세어주면 된다.

 

먼저 people 배열을 sort 하는데, 앞에서 무거운 사람부터 태우기 위해 reverse=True로 내림차순 정렬을 해준다.

 

그리고 뒤에서부터 가벼운 사람의 몸무게를 보면서

현재 보트에 태울지 말지 결정하면 되는데,

이 때 태운 사람은 제외하면 되므로,

start라는 변수를 만들어서 가벼운 사람의 인원을 -1씩 줄여나갈 예정이다.

 

people 배열을 for문을 돌려 앞에서부터 무거운 사람을 보고

아래에서 두 번째 for문으로 뒤에서부터 가벼운 사람의 몸무게를 비교한다.

 

만약, 남은 사람들 중 무거운 사람과 가벼운 사람을 보는 지점이 일치한다면,

모두가 구조되고 마지막 1사람만 남은 것을 의미하므로,

두 for문 사이에서 최종 ans에 +1한 다음 break로 종료하면 된다.

 

맨 앞(무거운) 사람을 기준으로 맨 뒷(가벼운) 사람과의 몸무게 합의 값을 보면서

구명보트 사용 개수와 남은 사람들을 계산해주어야 하는데,

구명보트가 최대 2명까지 수용할 수 있다고 했으므로,

무조건 for문이 돌면서 ans에는 +1해준다. 

 

즉, 현재 두 사람의 몸무게가 구명보트 limit 이하라면,

구명보트 1개를 사용(ans+1)하고 두 명 다 탈출에 성공했으므로,

가벼운 사람의 기준 점을 start-1로 한 단계 앞으로 옮겨주고,

무거운 사람의 기준점 또한 첫 번째 for문으로 한 칸 오른쪽 이동을 한다.

 

만약 현재 두 사람의 몸무게가 구명보트 limit 초과라면,

구명보트 1개를 사용(ans+1)하고 무거운 사람만 탈출할 수 있으므로,

가벼운 사람은 다음번 무거운 사람과 함께 타는 것을 기대해야 한다. 

따라서 그냥 break를 걸어주면 된다.

 

최종적으로 ans를 return하면, 

 

채첨결과: 정확성 테스트케이스 15개와 효율성 테스트케이스 5개 모두 잘 통과한다. 

 

 

[2차 시도]

def solution(people, limit):
    ans = 0
    people.sort(reverse=True)
    heavy = 0
    light = len(people)-1
    while heavy <= light:
        if people[heavy]+people[light]<=limit:
            light-=1
        ans+=1
        heavy+=1
    return ans

 

풀이: 이번에는 이중 for문을 쓰지 않고, while문을 한 번 써서 앞에서부터 무거운 사람과 뒤에서부터 가벼운 사람이 한 사람으로 일치할 때까지 반복한다.

 

만약 가장 무거운 사람과 가장 가벼운 사람의 몸무게가 limit 제한 이하라면,

가벼운 사람은 탈출했으므로, 그 다음 가벼운 사람으로 기준점을 -1 옮겨준다.

 

그리고 두 사람의 몸무게 합과 상관없이, 매 실행마다 구명보트 개수는 +1 늘어나고, 

가장 무거운 사람도 그 다음 무거운 사람으로 기준점을 +1 옮겨준다.

 

최종적으로 ans를 return하면, 

 

채첨결과: 정확성 테스트케이스는 변화가 미미하지만, 효율성에서 시간이 압도적으로 줄었다.

 

 

 

 

'쫄보의삽질' 블로그 탄생스토리가 궁금하다면:

Git push 취소 방법 (feat. '쫄보의삽질' 블로그 탄생 배경)