[Python3]프로그래머스_구명보트

문제출처: https://programmers.co.kr/learn/courses/30/lessons/42885

접근법

그리디 알고리즘 문제가 풀기는 쉽지만 효율적으로 코드를 짜기 쉽지 않은 것 같다.
처음에 보트에 "2명"만 탈 수 있다는 지문을 읽지 못한 것이 큰 실수였다.

1. 먼저,보트에 최대한 효율적으로 타야한다는 생각을 했다. 무게 제한이 100kg이라면 [80,10] , [70,30] 의 경우가 [80],[70,10] ,[30]의 경우가 될 수 있기 때문이다.
   이는 무거운 사람을 먼저 고려해야한다는 힌트였다.
   => 정렬

2. (오답) 무거운 사람부터 반복문을 돌며 list가 비어있지 않다면 list안의 어떤 숫자와 자신의 무게의 합이 limit을 넘지 않을 시 이는 한 쌍을 이뤄( 같은 boat ) list에서 제거 후 answer += 1 , 그런 경우가 없을 시 list에 자신의 무게를 append
   => 정답은 구할 수 있으나 중첩 반복문이 들어가며 효율성 탈락

3. 효율성을 위해 한번의 반복문을 통해 해를 얻어야 함을 직감했다. 테스트 케이스들을 풀어보며 보니 가장 무게가 많이 나가는 사람은 가장 적게 나가는사람과 타거나 혼자 타거나 이 두가지의 경우밖에 없었다. 이는 정렬을 할 시 양 끝쪽에서부터 비교하여 같은 보트에 탈 수 없다면 무거운 사람 혼자, 같이 탈 수 있다면 타면 된다는 사실을 알았다.
   => 투 포인터를 활용

코드

정답코드)

def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    i,j = 0,len(people)-1
    while( i < j ):
        if( people[i] + people[j] <= limit ):
            answer += 1
            j -= 1
        else:
            answer += 1
        i += 1
    return answer+1 if( i== j ) else answer

오답코드)

def solution(people, limit):
    answer = 0
    boat = []
    for p in sorted(people,reverse=True):
        flag = True
        if( boat ):
            for b in boat:
                if( b + p <= limit ):
                    answer += 1
                    boat.remove(b)
                    flag = False
                    break
        if( flag ):
            boat.append(p)
    return answer + len(boat)