[알고리즘 문제 풀이] - 구명보트

 

오늘도 코딩테스트 준비 겸 프로그래머스에서 문제를 풀어 보았습니다.

 

위에 사진은 보트에 관한 문제 풀이라서 넣어보았어요 ㅎ

 

 

 

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

 

즉, 필요한 구명보트의 개수를 최소값으로 줄이기 위해선 보트마다

 

최대한 주어진 무게 제한에 가깝게 채워야 된다는 얘기가 됩니다.

 

어떻게 2명을 선정할것인지가 관건인 문제네요. 2명을 선정하는 데에는 여러가지 방법이 존재 합니다.

 

제가 생각해낸 방법은 무게 제한을 넘지 않는 선에서

 

가장 무거운 사람과 가벼운 사람을 매치 시키는 방법 입니다.

 

예를 들면,

 

30kg, 50kg, 70kg, 50kg의 인원들이 있고 무게 제한이 100kg라면,

 

답은

이렇게 30kg와 70kg을 태워서 100kg를 만들고 50kg 2명을 태워서 100kg를 만드는 겁니다.

 

저는 2개의 list가 필요하다고 판단해서 빈 stack을 하나 만들었습니다.

 

그리고 기존의 리스트를 오름차순으로 정렬을 한 후 리스트의 pop()으로 무게가 높은 사람부터 낮은 순으로 

 

다른 스택으로 이동시킵니다.

 

이해를 돕기 위해 예시를 보여드리겠습니다.

 

스택 자료구조를 쓴 이유는 LIFO 이기 때문입니다.

 

정렬된 리스트에서 반이 스택으로 이동하였다면

 

2개의 중간값을 함께 보트에 태울수 있고 점차적으로 제거해나가다 보면

 

마지막에 가장 무거운 사람과 가벼운 사람이 남기 때문입니다.

<풀이>

def solution(people, limit):
    answer = 0
    people.sort()	#오름차순으로 정렬
    stack = []
    
    while people:
        in_boat = people.pop()	
        if stack and in_boat+stack[-1] <= limit:	#두명을 태울수 있을때
            answer += 1		#두명을 태운 한대의 보트가 출발
            stack.pop()
        else:
            stack.append(in_boat)
            
    return len(stack) + answer	#한명씩 타고 있는 보트의 수 + 2명씩 탄 보트의 수

채점을 해본 결과는....

 

효율성 테스트의 결과를 보니 시간복잡도가 굉장히 중요한 문제 같습니다.

 

스택 자료구조의 pop()과 append()는 시간복잡도가 O(1)이라는게 중요했던것 같습니다.

 

채점 후에 다른 분이 한 코드를 보니

 

굳이 또 다른 스택을 만들지 않고 인덱스를 2개중 한개는 리스트 앞에서부터 이동하고

 

다른 하나는 뒤에서 앞으로 오게 하는 방법을 쓰셨네요...

 

역시 고수는 많고 가야할 길이 먼것 같습니다 ㅎ