[알고리즘] 프로그래머스 | 구명보트

구명보트

탐욕법 Greedy 문제라고 적혀있다

 

답: 

from collections import deque

def solution(people, limit):
    count = 0
    people.sort()
    deq = deque(people)
    
    while deq: 
        weight = limit - (deq[0] + deq[-1])
        if weight < 0:
            count += 1
            deq.pop()
        else:
            count += 1
            deq.popleft()
            deq.pop()

        if len(deq) == 1:
            count += 1
            deq.pop()
            break
        
    return count

 

 

문제 분석 및 해석

 

구명보트 한 번에 최대 2명씩, 무게 제한도 있음

모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return

 

 

>> 풀이생각 첫 번째

탐욕법이지만 순서가 중요하지않으므로 

sort해서 하나씩 더해주고  limit에 맞는지 요소를 검사하고 

    1. limit와 weight += person 값을 검사하기

    2. limit - weight하고 0보다 작아지면...

count +=1하기, weight초기화 후 person 다시 더해 주기

 

 

>> 풀이생각 두 번째

라고 생각했지만 풀이 중에 많은 오류 / for문 하나인데도 효율성 검사를 대부분 통과하지 못하는 것을 보고

질문하기에서 풀이 방법 힌트를 얻었다..

https://school.programmers.co.kr/questions/54072

 

 

 

 

 

과정 1  # 제출 시 실패

 

weight를 빼서 계산하기 위해 변수를 지정하여 저장하고, people을 정렬해둠

def solution(people, limit):
    count = 0
    weight = limit
    people.sort()

 

 

아래 주석과 같이 생각하여 풀이했으나 처참한 실패를 겪음..

    for person in people:
        weight -= person # 반복문으로 도는 요소를 그때그때 빼주기
        if weight == 0: # 0과 같으면 count, weight를 limit으로 초기화
            count += 1
            weight = limit
        elif weight < 0: # 0보다 작으면 count 하고 현재의 person을 limit에서 뺀 것을 다시 저장
            count += 1
            weight = limit - person 
        else:
            count += 1 #마지막 사람 더하기
        return count

 

 

 

반례를 찾아보다 문제에 제한 2인이 있다는 것을ㅜㅜ 찾았다

 

그래서 같은 방식으로 풀이해보되 아래와 같이 코드를 재작성해보았다

def solution(people, limit):
    weight = limit
    
    people.sort()
    len_p = len(people)
    count = 0 if len_p % 2 == 0 else 1 
    # people이 홀수로 주어지는 경우 count+1을 하고 시작하도록 설계

    for i in range(0, len_p - 1, 2): #range를 2씩 건너뛰며 출력
        weight -= (people[i] + people[i+1]) # 앞에서부터 index로 2개씩 더해주고 출력해보려 했다
        if weight < 0: # weight 0보다 작을 경우 2명 모두 탈 수 없으므로 보트+2
            count += 2
        else:  # weight가 0보다 클 경우 2명 태우기, 보트 + 1
            count += 1
    return count

 

 

 

 

 

과정 2  # 방법을 찾아보고 풀이

 

한개의 for문으로 오류가 발생하는 것을 보고

내가 생각하지 못하는 방법으로 풀이하는 것이 아닐까?하는 생각에 풀이 도움을 받기로 했다.

 

1. 정렬과 deque를 사용해서 풀이한다

2. 가장 무거운 사람과 가장 가벼운 사람을 올려서 limit - 했을때 0 미만이면 무거운 사람을 먼저 보내는 방식으로 풀이하기

 

 

 

people을 정렬하여 deque로 만들었다

from collections import deque

def solution(people, limit):
    count = 0
    people.sort()
    deq = deque(people)

 

 

 

 

처음엔 index값을 늘려가며 계산해야한다 생각해 index 변수 i와 people length를 활용해 while문을 종료하고자 했다

풀이 과정에서 굳이 Index가 필요하지 않음을 인지하고 제거했다

i = 0
len_people = len(people) - 1 

while i < len_people: 
    ...
    i += 1

 

고친 코드

weight = limit - (deq[0] + deq[-1])
        if weight < 0:
            count += 1
            deq.pop()
        else:
            count += 1
            deq.popleft()
            deq.pop()

 

 

 

 

while조건에 deq와 연산자를 넣으려고 했더니 deque형식에는 연산자를 사용할 수 없다고해서

while문 안에 종료조건을 넣어주는 방식으로 풀이했다.

 

    while True: 
        ...
        len_d = len(deq)
        if len_d == 1:
            count += 1
            deq.pop()
            break
        if len_d == 0:
            break
        
    return count

 

 

 

이후 연산자를 사용하지 않고 내부에 요소가 있는지 없는지, boolean값으로 검사하는 방법을 알게되어

위 종료조건 일부를 지우고 리팩터링 할때 활용했다.

 

    while deq: 
        ...
        if len(deq) == 1:
            count += 1
            deq.pop()
            break
        
    return count

 

 

리뷰

풀이 방법을 생각하는 것이 아직 부족하다.

여러 문제를 많이 풀어보는 수 밖에

 

스터디 구경다니면서 새롭고 좋은 문제들을 많이 접하고 풀이할 수 있어서 재밌다:)