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

https://school.programmers.co.kr/learn/courses/30/lessons/42885#

프로그래머스

---

보트에 최대 2명의 인원제한이 있다는 조건만 잘 체크하면 될 것 같다.

 

처음에는 몸무게 오름차순으로 정렬하여 한번에 한 명 또는 두 명씩 태워주었는데,

그렇게 풀면 [10,20,30,40,50,60,70,80,90], 100 과 같은 테스트케이스에서 오답이 나온다.

 

그래서 몸무게 내림차순으로 정렬하고,

리스트의 맨 앞과 맨 뒤 (남은 인원 중 몸무게 최대인 인원과 최소인 인원) 을 한 번에 태울 수 있으면 태우고,

그렇지 않으면 맨 앞 인원만 태우는 방식으로 코드를 작성하였다.

 

python

def solution(people, limit):
    answer = 0
    people.sort(reverse = True)
    # 1명 또는 2명씩 태우기
    idx = 0
    while idx < len(people):
        if people[idx] + people[-1] <= limit:
            people.pop()
        idx += 1
        answer += 1
    
    return answer

 

다른 풀이중 나와 아이디어는 동일하지만, pop()을 쓰지 않고 투포인터를 써서 푼 코드가 있었다.

연산속도가 빨라서 효율성에서 거의 2배정도 차이가 났다. 훨씬 좋은듯!

def solution(people, limit):
    answer = 0
    people.sort(reverse = True)
    # 1명 또는 2명씩 태우기
    a = 0
    b = len(people)-1
    while a <= b:
        if people[a] + people[b] <= limit:
            b -= 1
        a += 1
        answer += 1
    
    return answer