[Python]구명보트

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

 

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

 

풀이 1. 큰 수에 작은 수를 더하기

-가장 무거운 사람과 가장 가벼운 사람을 더해주고

가능하면 조금 덜 가벼운 사람을 추가해서 배에 태우는 방법.

 

def solution(people, limit):
    answer = 0
    while len(people)>0:
        if len(people)==1:
            answer+=1
            break
            
        elif max(people)+min(people)>limit:
            answer+=1
            people.remove(max(people))
            
        else:
            answer+=1
            tmp=max(people)+min(people)
            people.remove(max(people))
            people.remove(min(people))
            
            while tmp < limit and len(people)>0:
                tmp+=min(people)
                if tmp>limit:
                    break
                elif tmp==limit:
                    people.remove(min(people))
                    break
                else:
                    people.remove(min(people))
    
    return answer

정확성은 성공!

효율성은 실패!

 

문제를 잘 읽자! 두명만 구명보트에 탈 수 있다.

Greedy 풀이!

풀이 1 개선

def solution(people, limit):
    answer = 0
    while len(people)>0:
        
        #구명보트(리스트)에 최고 중량의 사람을 태운다.
        #가장 가벼운 사람을 추가로 태운다.
        #리미트 전까지 태우고 태우면 구조되지 않은 사람들 목록에서 지운다.
        #정답횟수를 한번 더해준다.
        #최대 2명씩 밖에 탈 수 없고
        
        boat=[]
        answer+=1
        
        boat.append(max(people))
        people.remove(max(people))
                 
        if len(people)<=0:
            break
                
        boat.append(min(people))
        if sum(boat) > limit:
            continue
        people.remove(min(people))
        
    return answer

정확성은 성공!

효율성은 실패!

 

 

리스트 만들지 말고 더 간단하게!

def solution(people, limit):
    answer = 0
    while len(people)>0:
        
        #구명보트(리스트)에 최고 중량의 사람을 태운다.
        #가장 가벼운 사람을 추가로 태운다.
        #리미트 전까지 태우고 태우면 구조되지 않은 사람들 목록에서 지운다.
        #정답횟수를 한번 더해준다.
        #최대 2명씩 밖에 탈 수 없고
        
        answer+=1
        tmp=max(people)
        people.remove(max(people))
                 
        if len(people)<=0:
            break
                       
        if tmp+min(people) > limit:
            continue
        people.remove(min(people))
        
    return answer

정확성 성공!

효율성 실패!(개선은 됐음)

 

큐 형태로 pop을 써서 효율성을 높이자

def solution(people, limit):
    
    #구명보트(리스트)에 최고 중량의 사람을 태운다.
    #가장 가벼운 사람을 추가로 태운다.
    #리미트 전까지 태우고 태우면 구조되지 않은 사람들 목록에서 지운다.
    #정답횟수를 한번 더해준다.
    #최대 2명씩 밖에 탈 수 없고
    #큐와 같이 pop을 이용한 효율성 향상
    
    answer = 0
    people.sort()
    while len(people)>0:
        
        answer+=1
        tmp=people.pop()
                 
        if len(people)<=0:
            break
                       
        if tmp+min(people) > limit:
            continue
        people.pop(0)
        
    return answer

정확성 성공!

효율성 실패!(개선은 됐음)

 

데크/디큐 Dequeue 를 써봤지만 효율성 실패!

from collections import deque

def solution(people, limit):
    
    #구명보트(리스트)에 최고 중량의 사람을 태운다.
    #가장 가벼운 사람을 추가로 태운다.
    #리미트 전까지 태우고 태우면 구조되지 않은 사람들 목록에서 지운다.
    #정답횟수를 한번 더해준다.
    #최대 2명씩 밖에 탈 수 없고
    #큐와 같이 pop을 이용한 효율성 향상
    
    answer = 0
    boat=deque(sorted(people))
    
    while len(boat)>0:
        
        answer+=1
        tmp=boat.pop()
                 
        if len(boat)<=0:
            break
                       
        if tmp+min(boat) > limit:
            continue
        boat.popleft()
    
    return answer

 

하....

그냥 리스트 번호 이동으로

큐의 pop보다 더 빠른 속도를 내게 한다.

 

def solution(people, limit):
    
    #구명보트(리스트)에 최고 중량의 사람을 태운다.
    #가장 가벼운 사람을 추가로 태운다.
    #리미트 전까지 태우고 태우면 구조되지 않은 사람들 목록에서 지운다.
    #정답횟수를 한번 더해준다.
    #최대 2명씩 밖에 탈 수 없다.
    #리스트 정렬후 삭제하지 말고 번호 이동으로 데이터 처리.
    
    answer = 0
    boat=sorted(people)
    left=0
    right=len(people)-1
    
    while 1:
        answer+=1
        right-=1
        if left>right:
            break
                       
        if boat[left]+boat[right] > limit:
            continue
        left+=1
        
    return answer

성.공.