[PG] 구명보트

문제

me

faillog

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort()
    boats=deque()
    cnt=0
    for p in range(len(people)-1,-1,-1): # sort reverse 안쓰려고 뒤에서부터 index함
        isFit=0
        while isFit < len(boats): # 배 몇개 검사했는지 확인
            if people[p] <= boats[0]: # 보트 남은 무게보다 작을 경우 태울 수 있음
                cnt+=1
                isFit="done"
                boats.popleft()
                break
            else: # 태울 수 없음
                isFit+=1
                boats.rotate(-1) # 맨 앞을 맨 뒤로 보냄
        if isFit!="done" : # done이 아니라면 들어갈 곳이 없었으니 보트 하나 만들어주기
            if limit-people[p]+people[0]>limit: # 그 값이 너무 커서 가장 작은 값이 들어가도 limit을 넘친다면
                cnt+=1
            else: boats.append(limit-people[p]) # 태우고 남은 무게
    return len(boats)+cnt

• 효율성이 통과가 안된다.. 나름 소모될 건 다 뺐다고 생각했는데..

solutions

def solution(people, limit):
    answer = 0
    people.sort()
    left = 0
    right = len(people) - 1
    while left < right:
        if people[left] + people[right] <= limit:
            left += 1
            right -= 1
        else:
            right -= 1
        answer += 1
    if left == right:
        answer += 1

    return answer

pop을 사용하지 않고 left, right 변수로 남은 사람 중 가장 가벼운 사람과 무거운 사람을 가리키게 해서 해결하는 방법입니다.

people 오름차순 정렬

left는 0, right는 len(people) - 1의 값을 초기값으로 가짐.

남은 사람들 중, 가장 무거운 사람과 가장 가벼운 사람 무게의 합이,
3-1 limit값 이하일 경우, left는 1 더하기, right는 1 빼기
3-2 limit보다 클 경우, right만 1 빼기

3번 과정을 left가 right보다 작을 때 까지 반복하고, 매 반복 때 마다 answer에 1 더하기

반복을 마친 뒤, left가 right가
5-1 같으면, 한 명이 남은 것이니 answer에 1 더하기
5-2 left > right면, 모두 보트를 타고 나간 뒤므로 answer 그대로