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

 

풀이방법

보트의 개수를 최소로 만들기 위해서는 가능하다면 1개의 보트에 2명씩 태워야한다! 즉, 몸무게가 많이 나가는 사람을 태울 경우에 몸무게가 적은 사람들 중 같이 태울 수 있는 사람을 찾으면 유리할 것 같다고 생각하여 몸무게가 담긴 배열을 정렬하고 투 포인터를 사용했다 :)

1. 몸무게가 담긴 배열 오름차순 정렬

2. 아직 보트에 타지 않은 사람들 중 몸무게가 가장 적은 사람을 가리키는 포인터 left, 몸무게가 가장 많은 사람을 가리키는 포인터 right 선언

 

3. left가 가르키는 몸무게와 right가 가르키는 몸무게의 합이 limt 이하라면 그 두명을 태우고 left는 다음으로 몸무게가 적게 나가는 사람, right는 다음으로 몸무게가 많이 나가는 사람을 가르키도록 움직인다.

 

4. left가 가르키는 몸무게와 right가 가르키는 몸무게의 합이 limt 보다 크면 몸무게가 가장 많이 나가는 사람을 태우고 right를 다음으로 몸무게가 많이 나가는 사람을 가르키도록 움직인다.

 

5. 3,4의 과정을 left와 right가 엇갈릴때까지 반복한다. (left와 rigth가 엇갈린다는 의미는 모든 사람을 다 태웠다는 의미이기때문에!)

 

코드_Java

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        
        int answer = 0;
        int left = 0, right = people.length - 1;
        while(left <= right) {
            if(people[left] + people[right] <= limit) left++;
            right--;
            answer++;
        }
        
        return answer;
    }
}

 

코드_Python

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

---

https://programmers.co.kr/learn/courses/30/lessons/42885?language=python3 

코딩테스트 연습 - 구명보트