[python] 프로그래머스 - 구명보트

 

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/42885

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

 

 

첫 번째 풀이 : 효율성 테스트 실패

 

def solution(people, limit): 
    people.sort()

    count = 0
    
    while len(people) > 0:
        sum_w = 0
        max_val = people.pop()
        sum_w += max_val
        
        for index in range(len(people) - 1, -1, -1):
            if limit - sum_w >= people[index]:
                sum_w += people[index]
                people.pop(index)
                break
        
        count += 1
    
    return count

 

아니 난 효율성 테스트가 있는지 몰랐지. 먼저 한 번 돌려볼걸.

이 풀이의 시간 복잡도는 O(N^2)이다.

사고방식은 가장 무게가 무거운 사람과 무게가 싣고 남은 무게에 탈 수 있는 사람 중 가장 무거운 사람을 태우는 횟수이다.

 

두 번째 풀이 : 효율성 테스트 실패

 

def solution(people, limit): 
    people.sort(reverse=True)

    count = 0

    while True:
        boat = limit
        
        for index in range(len(people)):
            if people[index] > 0 and boat - people[index] >= 0:
                save_index = index
                boat -= people[index]
                people[index] = -1
                break
                
        if save_index < 0:
            break

        for index in range(save_index + 1, len(people)):
            if people[index] > 0 and boat - people[index] >= 0:
                save_index = -1
                people[index] = -1
                break
                
        count += 1
        save_index = -1
    
    return count

 

이 풀이도 마찬가지로 O(N^2)이다.

혹시나 pop(index)가 O(N) 시간만큼 걸리기 때문에 싶어서 한 번 바꿔봤는데 역시나 실패한다.

그리고 살펴보니 첫 번째 풀이는 pop을 통해서 원소 개수를 줄이기 떄문에 오히려 더 빠르다...

 

세 번째 풀이 : 참고하기 참고

 

def solution(people, limit): 
    people.sort(reverse=True)

    count = 0
    
    left_index = 0
    right_index = len(people) - 1
    
    while True:
        if left_index >= right_index:
            if left_index == right_index:
                count+= 1
            break
            
        if people[left_index] + people[right_index] <= limit:
            left_index += 1
            right_index -= 1
        else:
            left_index += 1
        
        count += 1
            
    return count

 

pop()을 사용하지 않고 도대체 어떻게 풀어야하는지 끙끙 앓다가 결국 포기하고 참고하기를 봤다.

그리고 깨달은 점. 그냥 젤 무거운 사람이랑 젤 가벼운 사람 실으면 되는 거였다.

 

풀이와 같이 index를 양 끝에서 이동시키는 원리는 퀵 정렬에서도 똑같이 쓰이는 것으로 알고 있다.

 

---

 

시간 복잡도

 

첫 번째 풀이와 두 번째 풀이의 경우 O(N^2)

세 번째 풀이는 O(N)이다.

 

두 번째 풀이의 경우 탐색 범위가 전혀 줄어들지 않아서 가장 오래 걸렸고,

첫 번째 풀이의 경우 탐색 범위가 두 개씩 줄어들지만 pop(index) 함수에서 시간이 오래 걸렸다.

세 번째 풀이의 경우 탐색 범위도 2개씩 줄어돌고 시간 복잡도도 O(N)이다.

 

다른 사람의 풀이를 보면서 알게 된 점

 

-

 

고찰

 

탐욕법 카테고리에 속하는 문제이다.

풀면서 느낀건데 탐욕법에서 핵심은 내가 생각한 방법으로 하는게 최선임을 확인할 수 있니?인 것 같다.

 

처음에는 무게를 빨리 줄일수록 이득이라고 어렴풋이 생각해서 일단 무거운 사람 위주로 선택해서 카운팅했는데

이 문제의 조건 중 보트에는 한 번에 2명 씩 밖에 탈 수 없다. 라는 조건이 있다.

애초에 사람 무게를 나눌 수 없기도 하거니와, 위 말 때문에 무게가 얼마든 결국 2명밖에 싣지 못해서 

무게를 줄이는 것이 중점이 아니라 인원을 어떻게 빨리 줄일까를 생각해서 풀어야하는데

이를 하지 못하고 무게에 중점을 둔 것이 원인이라고 파악된다.

 

예를 들어 500원, 100원, 50원으로 거슬러 줄 때 최소 개수의 동전으로 거슬러줘야하는 문제를 보면

 

1. 동전의 개수를 최소로 줄여야 한다.

2. 가치가 큰 동전부터 먼저 거슬러준다. (큰 수가 작은 수의 배수기이 때문)

 

와 같이 1. 무엇을 2. 어떻게 줄일지가 최선인가?를 따지는 것이 핵심인데

나는 1. 무엇을 제대로 설정하지 못한 것이다.

이 부분은 항상 자연스럽게 넘어가서 미처 고려해보지 못했는데 이를 계기로 체크하고 넘어가야겠다.