[프로그래머스/Python] 구명보트 - Level2

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

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

 

처음 생각한 문제 풀이는 people 리스트를 오름차순으로 정렬한 다음 최소값 두 개를 가져와 limit보다 크면 최소값 하나만 리스트에서 빼고 limit보다 작거나 같으면 최소값 두 개를 리스트에서 빼는 로직으로 코드를 짰다. 그런데.... 일부는 맞았지만 일부는 실패가 떴다..ㅠㅠ

질문하기를 보니 내가 생각한 로직이 틀린거 였다...

 

필요한 구명보트의 개수의 최소값을 구하려면 people 리스트를 오름차순으로 정렬한 후 최소값과 최대값을 가져와 limit보다 크면 최대값을 리스트에서 빼고 limit보다 작거나 같으면 최소값과 최대값을 리스트에서 빼야했다. 다음이 이 로직으로 코드를 짠 것이다.

def solution(people, limit):
    answer = 0
    
    people.sort() # 오름차순 정렬
    
    while people:
        if len(people) == 1: # 마지막 값 하나만 남았을 때
            people.pop(0)
            answer += 1
            return answer
        
        if people[0] + people[-1] > limit: # 최소값 + 최대값 > limit 인 경우
            people.pop()
            answer += 1
        else: # 최소값 + 최대값 <= limit 인 경우
            people.pop(0)
            people.pop()
            answer += 1
    
    return answer

이렇게 코드를 짰더니 정확성 테스트는 다 통과했지만 효율성 테스트에서 하나가 시간 초과가 났다... 질문하기에서 그 이유를 찾아보니 pop() 때문이었다 그래서 로직은 똑같지만 left, right 변수를 두어 코드를 바꾸어야 했다.

 

 

최종 코드

def solution(people, limit):
    answer = 0
    left = 0 # 남은 사람들 중 최소값
    right = len(people) - 1 # 남은 사람들 중 최대값
    
    people.sort() # 오름차순 정렬 
    
    while left <= right:
        if left == right: # 마지막 사람인 경우
            answer += 1
            return answer
        
        if people[left] + people[right] > limit: # 최소값 + 최대값 > limit 인 경우
            right -= 1
            answer += 1
        else: # 최소값 + 최대값 <= limit 인 경우
            left += 1
            right -= 1
            answer += 1
    
    return answer

left는 구명보트를 타지 않고 남은 사람들 중 가장 가벼운 사람(최소)을 가리키는 변수이고, right은 구명보트를 타지 않고 남은 사람들 중 가장 무거운 사람(최대)을 가리키는 변수이다. people 리스트를 오름차순으로 정렬한 다음 구명보트의 최소값을 구한다.

 

left == right는 마지막 한 사람만 남은 경우이므로 answer에 +1을 해주고 바로 답을 리턴한다. 최소 + 최대가 limit보다 큰 경우에는 가장 무거운 사람(최대)만 구명보트를 탈 수 있으므로 right에 -1을 해준다. 최대 + 최소가 limit보다 작거나 같은 경우 가장 무거운 사람(최대)과 가장 가벼운 사람(최소) 모두 구명보트를 탈 수 있으므로 left에 +1, right에 -1해준다. 이것을 반복하다보면 left > right가 되므로 while문을 빠져나오게 된다.

 

다른 사람 풀이를 찾아보니 내가 코드를 짠 로직과 같지만 좀 더 간단하게 코드를 짰다. 참고하면 좋을 것 같다.

def solution(people, limit): 
    answer = 0 
    people.sort() 
    start, end = 0, len(people) - 1 
    
    while start <= end: 
        answer += 1 
        
        if people[start] + people[end] <= limit: 
            start += 1 
        
        end -= 1 
        
    return answer

출처: https://somjang.tistory.com/entry/Programmers-구명보트-Python [솜씨좋은장씨]