[프로그래머스] 구명보트 - 파이썬(Python3)

프로그래머스 level 2 구명보트

-> https://programmers.co.kr/learn/courses/30/lessons/42885

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

이번에 풀어볼 문제는 구명보트 문제입니다.

문제 분류가 그리디로 되어있지만,

 

적혀있지 않아도 그리디를 떠올려야 합니다.

 

같이 한번 풀어봅시다.

---

풀이 아이디어

첫번째로 든 생각

-> 그냥 작은애들부터 태울 수 있는만큼 태워서 보낸다.

하지만 최대무게 제한이 150이고 50 70 80 100 처럼 돼있으면 (50, 70), (80), (100) 순서로 탈출하지만

실제 답은 (50, 100),  (70, 80)으로 2번만에 탈출 가능하므로 첫번째 생각은 틀렸습니다.

 

그리고 첫번째 생각에서 틀린점을 보안하기 위해 든 생각.

-> 가벼운것부터 말고, 최대한 리밋에 가깝게 채우면 어떨까?

 

그리고 이 생각에 도달한 순간, 이미 문제는 풀렸습니다.

 

최대한 리밋에 가깝게 채울려면...

무거운 사람들부터 태우고, 

그 다음 자리가 비면 가벼운 사람을 태우자!

 

그럴듯한 방법 같습니다.

바로 구현해보고 생각합시다.

---

 

 

구현

---

먼저 무거운놈, 가벼운놈을 차례대로 지지고 볶으니까 정렬을 해줍시다(내림차순).

그러면 무거운 사람이 제일 앞쪽에 있고, 가벼운 사람이 제일 뒤에 있습니다.

 

그러므로 제일 앞쪽에 있는 놈을 태웁시다. list.pop(0)을 이용하여 구현 가능합니다.

 

그리고 제일 제일 가벼운놈을 태웠을때 리밋을 넘는다면, 무거운놈 혼자 탈출하고

리밋을 넘지 않는다면 최대 2명이므로 같이 탈출하면 됩니다. list.pop()을 이용하여 구현 가능합니다.

 

이걸 다 탈출할때까지(list가 빌때까지) 반복하고,

반복할때마다 탈출 횟수를 저장하고 마지막에 리턴해주면 되겠네요 !

 

그렇게 구현한 코드

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

 

이렇게 제출했더니 이게 웬걸 !

이게 왜 시간초과가 뜨지..? 정확성 테스트도 꽤 빠르게 끝났고 정렬 제외하면 시간복잡도도 충분히 적은데 말이죠..

그래서 똑같은 방식이지만 조금 다르게 바꿔봤습니다.

 

h는 앞쪽부터 제일 무거운 사람을 가리키는 인덱스,

l은 뒤쪽부터 제일 가벼운 사람을 가리키는 인덱스입니다.

 

만약 h==l 일때 n+1리턴하고 h>l일때 n을 리턴하는것은 스스로 생각해보시길 바랍니다.

def solution(people, limit):
    people.sort(reverse=True)
    
    n = 0
    h, l = 0, len(people)-1
    while people:
        n += 1
        boat = people[h]
        h += 1
        
        if boat + people[l] <= limit:
                l -= 1
        
        if h == l:
            return n+1
        elif h > l:
            return n

이렇게 바꾸니까 상당히 빨라졌는데...pop도 어차피 O(1) 아닌가요?? 어째서 두배나 차이나는건지..!

효율성 테스트 제한이 너무 빡센 것 같습니다..ㅠㅠ