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

문제

 

 

문제를 요약하자면 최대 2명이하의 사람을 한 대의 보트에 담는데 보트의 무게제한을 넘지 않으면서 전부를 태울 수 있는 보트의 개수 최솟값을 구하는 문제이다.

 

처음 생각한 방법은 일단 사람을 무게순으로 정렬을 한뒤 맨앞과 맨뒤 이 두개의 시작점부터 중간점으로 나아가는 방식으로 개수를 구해주려고 했다

 

초기코드(오답)

def solution(people, limit):
    answer = 0
    people.sort(reverse = True)
    s = 0
    e = len(people)-1
    while(s<e):
        #두 명 담을때
        if people[s]+people[e] <= limit:
            s+=1
            e-=1
            answer+=1
        #한명만 담을 때
        else:
            s+=1
            answer+=1
    #한명 남은채로 끝났을 때 예외처리       
    if len(people)%2 == 1 and s==e:
        answer+=1
    
    
    return answer

 

 

하지만 하나의 테스트케이스에서 실패가 뜨고 효율성측면에서 실패가 떴다..

 

그래서 이 방법을 기본토대로 큐를 사용해서 해결해줘야겠다는 생각이 들었다.

 

 

 

정답코드 (큐 사용)

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort(reverse = True)
    s = 0
    e = 0
    q = deque(people)

    while(q):
        #남은 사람이 2명이상일때
        if len(q)>=2:
            s = q.popleft()
            e = q.pop()
            
            #두명을 한 보트에 넣는 경우
            if s+e <= limit:
                answer+=1
            #한명만 한 보트에 넣는 경우
            else:
                answer+=1
                q.append(e)
        #남은 사람이 한명일때
        else:
            s = q.popleft()
            answer+=1
    
    return answer

 

 

이런식으로 일단 처음에 people 리스트를 queue에 다 담아준 후 pop을 한 다음에 조건에 맞는지 따져본 후 조건에 맞지 않아서 보트에 태울 수 없는 경우에는 다시 넣어주어 다음번에 확인해주도록 해주었다.

 

 

그리고 남은 사람이 한명인 경우에는 시작점과 끝점 두개를 보는게 아니라 하나만 pop 해서 바로 넣어주면 되기 때문에 이 부분 또한 예외처리가 필요하다.

 

 

일단 이 문제는 러프하게 틀을 잡아놓은 후 오류가 나는 부분을 보완하기 위해 queue 를 사용해서 오류를 해결해주어야 겠다고 생각이 들었다는 점에서 의미가 있는 문제인 것 같다.

 

앞으로도 에러가 발생하면 단순히 이 방법이 틀렸다고만 생각하기보다는 기존의 풀이를 응용해서 새로운 정답을 도출할 수 있도록 생각해내는 것이 중요한 것 같다.