프로그래머스 42885 구명보트 파이썬 풀이

난이도 : Lv. 2

풀이일 : 2501164

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

프로그래머스

---

문제

---

아이디어

• people을 정렬한다.
• 가장 가벼운 사람과 가장 무거운 사람을 짝지어 두 사람 무게의 합이 무게 제한을 넘어가는지 확인한다.
• 무게 제한을 초과한다면, 무거운 사람은 혼자 타야한다. 현재 가벼운 사람과 다음 무거운 사람을 짝지어 비교하고 구명 보트 수를 한 개 더한다.
• 무게 제한을 초과하지 않는다면, 현재 가벼운 사람과 현재 무거운 사람이 함께 보트를 탄다. 다음 가벼운 사람과 다음 무거운 사람 짝을 지어 비교할 수 있도록 준비한다.

---

코드

def solution(people, limit):
    answer = 0
    
    people.sort()
    front, rear = 0, len(people) - 1 # 인덱스
    
    while front <= rear:
    	# 두 사람 무게 합이 제한을 넘지 않을 때
        if people[front] + people[rear] <= limit:    
            front += 1
        rear -= 1
        answer += 1
    
    return answer

• front, rear : 각각 가벼운 사람, 무거운 사람의 인덱스가 된다. 가장 가벼운 사람, 가장 무거운 사람부터 시작해 front는 하나씩 증가, rear는 하나씩 감소한다.
• while : 사람이 홀수일 경우도 있으니 <= 조건을 사용한다.
  • front, rear가 가리키는 사람의 무게 합이 무게제한을 초과하지 않는다면, front + 1, rear - 1을 하고 보트를 하나 더한다.
  • 두 사람의 무게 합이 무게제한을 초과한다면, 무거운 사람이 혼자 보트를 타, rear - 1을 하고 보트를 하나 더한다.

---

제출 결과

---

느낀점

• 일단 풀고 왜 그리디 분류길래 왜 그리디 알고리즘인지 찾아보았다. 근데 내가 푼 방식이 그리디라네...!
• 알고리즘을 좀 분류별로 공부를 하면서 풀어야겠다는 다짐을 한다.