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

[코테리뷰]

접근 방식

• 그리디 = > 구명보트에 2사람이 같이 탈 수 있는 조건 : 보다 무거운 사람은 보다 가벼운 사람과 탈 수 있다는 가정 성립

• 그래서 인덱스를 앞뒤로 좁혀나가서 같이 탈 기준(limit보다 무게가 같거나 적은지)으로 비교해줌.

  • 비교 ok : 서로 인덱스 +1/-1

  • 비교 not ok : 끝의 인덱스 -1

내 코드

• sort를 해주고, deque를 사용함

from collections import deque


def solution(people, limit):

    alone, together=0,0 # 따로, 둘이 같이 타는 경우의 수 변수
    queue = deque(sorted(people)) # 오름차순으로 정렬
    lightest = queue.popleft()  # 가벼운 사람

    while lightest:
        if not queue: # 큐가 (비교대상이) 더이상 존재하지 x
            alone+=1
            break
        heaviest = queue.pop()  # 무거운 사람
        sum = lightest+heaviest # 비교할 대상 : 두 사람의 무게 합
        if sum <= limit: # 같이 탈 조건 : limit보다 적을 때 같이 타기
            together+=1
            if not queue: # empty pop - 오류 방지
                break
            else:
                lightest = queue.popleft()
        else: # 무거운 사람 혼자 보트 타기
            alone+=1
    answer=alone+together
    return answer

내코드의 문제점 :

• 큐를 이용하다보니 큐가 더이상 존재하지 않을 때 ( 비교대상이 없거나, 비교 자체가 끝났을 때의) 처리를 각각 해주어야지 제대로 된 답이 도출된다. (이 오류를 잡느라고 시간을 오래씀) & 직관적으로 코드를 볼 때 어려움! ㅜㅜ

다른 분 코드

• 내 코드보다 직관적으로 이해가능!

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

    first = 0
    last = len(people) - 1
    while first < last:
        if people[first] + people[last] <= limit:
            first += 1

        last -= 1

        count += 1

    if first == last:
        count += 1

    return count