Programmers / 구명보트 / Python 파이썬

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 구명보트 (2단계)

문제 사이트:  https://programmers.co.kr/learn/courses/30/lessons/42885

---

모범 답안

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

주어진 정렬을 sort하여 오름차순으로 만든 다음에 가장 가벼운 사람과 가장 무거운 사람의 몸무게를 차례대로 더해가며 limit보다 작거나 같으면 같이 보내고, 무거우면 제일 무거운 사람부터 차례대로 보내는 방식이다.

 

 몸무게 오름차순으로 정렬된 배열에서 i는 ->방향, j는 <-방향으로 진행되면서 보트가 허용하면 보내고, 아니면 j부터 보내고, j가 i를 추월하는 순간 모든 검사가 끝난 것이므로 반복문을 종료한다. 이러한 문제 유형은 기본기문제에 있다.

 

 

나의 풀이

 

문제 풀었던 과정:

 

처음에는 큐를 이용해서 sort로 몸무게가 작은 사람 순서로 정렬하고, 첫번째 사람부터 차례대로 큐에 넣어 총합을 매번 검사한다. 총합이 limit보다 작으면 큐에 계속 넣고, 총합이 limit 과 같으면 큐를 초기화하고 카운트를 1회 추가해준다.

만약 총합이 limit보다 커지는 지점이 생기면 앞의 수들을 pop(0) 하고 카운트를 1회 추가한다.

 

그런데 너무 복잡하게 생각해서인지 자꾸 문제를 푸는데 오류가 났다. 나중에 보니 푸는 과정도 테스트 문제에만 허용되지, 다른 케이스에는 전혀 도움되지 않는 풀이었다.

 

기본기 문제를 풀었을 때처럼 i와 j를 이용하여 리스트 인덱스에 방향을 부여해서 풀면 쉽게 풀린다.

 

---