LV2 구명보트 (Python)

 

---

 

문제

 

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

프로그래머스

 

풀이

대놓고 그리디라고 적혀있어서 그리디 방식으로 접근했다.

 

"인원은 최대 2명"

"무게는 limit 초과 되면 안됨"

 

두가지의 조건을 가지고 풀어야 한다.

 

 

그리디 방식으로 보트를 최소한으로 띄울려면 한 보트안에 몸무게가 많이 나가는 사람1명 + 몸무게가 적게 나가는 사람1명 방식으로 태워야 한다.

 

따라서 우선 몸무게가 큰 순으로 정렬을 했다. 다음에는 포인터를 두개 두었다.

하나는 무거운 몸무게가 있는 앞쪽, 그리고 하나는 가벼운 몸무게가 있는 뒤쪽에 배치했다.

 

이후에 한명씩 태우면서 검사하는 식으로 풀이했다.

 

우선 앞쪽 포인터로 몸무게가 비교적 무거운 사람을 태운다. (이후 포인터를 이동한다.)

그 다음에 뒤에 포인터로 몸무게 가벼운 사람을 태울 수 있는지 검사한다.

 

만약 몸무게 가벼운 사람도 태울 수 있다면 뒤쪽 포인터도 앞으로 땡긴다.

태울수 없다면 패스해주고, 다음에 탈 수 있는 기회를 노려야한다. (우리가 고른 사람은 몸무게가 가장 가벼운 사람이다. 다른 사람을 탐색해서 현재 보트에 태울 수 있는지 검사할 필요가 없다.) 

그리고 정답을 +1 해준다.

 

이런식으로 반복문을 돌아주면 된다.

 

단, 이 문제는 앞 포인터만 계속 증가할 수 있다. (예로 people이 [70, 70, 70] limit이 70이면 앞 포인터만 계속 증가한다. )

따라서 둘이 같은 경우에도 체킹을 할 수 있게 조건을 설정해주어야 한다.

 

 

코드

def solution(people, limit):
    # 큰 사람부터 탑승
    people.sort(reverse=True)
    # 초기화
    answer = 0
    front = 0
    back = len(people)-1
    
    while front <= back:
        now = people[front]
        front +=1
        
        if now + people[back] <= limit:
            back -=1
        answer +=1
    
    return answer

 

후기

 

투포인터로 초반에 접근했다가 조건 잘못줘서 한참 돌아와서 다시 투포인터로 풀었다..