[프로그래머스 / Java] 구명보트 (Lv.2)

문제 풀이 날짜: 2023.05.05

포스트 작성일: 2023.05.06

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

프로그래머스 코딩테스트 고득점Kit 그리디 편 : 구명보트 (Lv.2) (문제 링크)

 

키워드

그리디, 투포인터

 

풀이 접근법

• 보트에는 한 번에 최대 2명씩만 탈 수 있다는 점에 유의하자.
• 입력의 수는 1 ≤ n ≤ 50,000 이므로, 50,000 × 50,000 = 2,500,000,000 으로 10^9 시간을 초과한다. 따라서 O(n²) 시간을 넘지 않는 방식으로 풀이해야 한다.
• 보트의 무게 제한을 넘기지 않으려면 가능한 가벼운 사람과 무거운 사람을 함께 태워 보내야 한다. ⇒ 주어진 인원의 무게를 오름차순으로 정렬해서 양 끝을 탐색한다.
• 배열을 정렬하였으므로 왼쪽 포인터와 오른쪽 포인터가 가리키는 사람을 함께 태울 수 있는지의 여부를 체크한다.
• 만약 두 사람을 함께 태울 수 없다면 맨 오른쪽의 무거운 사람을 먼저 보트 하나에 태워보내고(right += 1) 다음 사람들의 무게를 체크한다.
• 둘 다 태울 수 있다면 해당 2인을 태우고 양쪽의 인덱스를 모두 증가시킨다. (left += 1 & right += 1)
• 두 포인터가 만나는 지점까지 탐색하면 종료된다. (같은 사람을 가리키게 되면 종료)

 

코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;

        Arrays.sort(people);

        int left = 0;
        int right = people.length - 1;

        while(left <= right) {
            if(people[left] + people[right] <= limit) { 
                left += 1;
            }
            right -= 1;
            answer += 1;
        }

        return answer;
    }
}

---

 

처음에는 배열을 정렬한 뒤 맨 앞부터 두 명씩 가벼운 사람을 태우는 방식으로 풀었는데 대부분의 테스트 케이스에서 틀렸다. 반례를 찾아보니 인접한 무게의 사람들끼리 태우는 것으로는 해를 구할 수 없어, 투포인터로 바꿔 풀었다. 

 

Git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day3/Lifeboat.java