구명보트

작성일: 2024-10-30

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42885

접근 방식

먼저 내림차순으로 배열을 정렬해서, 보트에 최대한 탈 수 있도록 한다.

이전에 보트에 탄 사람과 더 했을 때, limit을 넘어간다면, 따로 태워보낸다.

잘못된 접근

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int answer = 0;
        int sum = 0;
        for(int p:people){
            if(sum+p<=limit) sum+=p;
            else{
                answer++;
                sum=p;
            }
        }
        return sum!=0?answer+1:answer;
    }
}

주어진 테스트케이스는 통과했으나, 채점 결과 22점밖에 나오지 않았다.

사실상 틀린 로직이다.

1시간 이상 생각해봤으나, 답이 생각나지 않아 인터넷의 도움을 받았다.

잘 된 접근

투 포인트를 이용하면 쉽게 문제를 풀 수 있었다.
(최대 두 명을 태울 수 있기 때문에 둘 다 태운다는 것을 가정)

먼저, 배열을 오름차순으로 정렬한다.

1. 이후에, 왼쪽(작은 수)과 오른쪽(큰 수) 을 더한 값이 limit보다 작거나 같은지 확인한다.

2. 만약 작거나 같다면, 태울 수 있다는 것이므로 left와 right를 가운데로 하나씩 옮긴다.

3. limit도 크다면, 큰 수만 태우는 것이 이득이다. 따라서 큰 수만 가운데로 하나 옮긴다.

4. 위 로직을 완료하면, answer+1을 함으로써 보트를 하나 완성한다.

1, 2, 3, 4를 왼쪽(작은 수)이 오른쪽(큰 수)보다 작거나 같은 경우에만 반복하도록 while문 조건을 건다.

마지막으로 answer를 리턴한다.

결과

소스 코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);  // 오름차순 정렬
        int answer = 0;
        int left = 0;
        int right = people.length - 1;

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

        return answer;
    }
}

알게 된 점

최대 두 개의 수를 이용한 합을 통한 문제 해결이 요구되는 경우에는

투 포인트를 이용하면, 간단하게 해결 할 수 있다.