[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 구명보트

<프로그래머스 문제풀이>

<출처 : 프로그래머스(Programmers)>

 

---

해답)

def solution(people, limit):
    people.sort()
    boat = 0
    last_index = len(people)-1
    for i in range(last_index):
        for j in range(last_index, i-1, -1):
            boat += 1
            last_index -= 1
            if people[i] + people[j] <= limit:
                break
    return boat

 

풀이)

 

1. 사람 무게를 오름차순 정렬을 합니다.

2. 가장 가벼운사람과 가장 무거운사람 순으로 같이 탈 수 있는 지를 검사합니다.

2-1. 같이 탈 수 없을 경우

=> 무거운사람에게 1인용 보트를 준 후(boat +=1) 방금 검사했던 가벼운사람과 그 다음 무거운 사람을 다시 검사합니다.

2-2. 같이 탈 수 있을 경우

=> 두 사람에게 보트를 1개 준 후(boat +=1), 다음으로 가벼운사람과 다음으로 무거운 사람을 검사합니다.

3. 루프가 다 돌았으면 , boat를 리턴합니다.

 

* 첫번째 for문이 처음 설정된 last_index 까지 갈 필요가 없는데  last_index가 변경될때마다 해당 for문도 변경이 되는지를 모르겠네요. 아시는 분은 조언 부탁드립니다..

 

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges