[프로그래머스 / 탐욕법(Greedy) / 자바(JAVA)] 구명보트

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

프로그래머스

 

풀이

로직

• 처음에는 정렬하고나서 limit의 무게가 될 때까지 가벼운 사람부터 채우는 방식을 선택했었다.
  하지만 이 방법으로는 결과가 나오지 않았음.
  그래서 핵심 아이디어를 보고 코드를 짰다.
  왜 이렇게 해야만 최적의 결과가 되는지는 아직까지 이해가 잘 가지 않는다... ㅠㅠ
• 아! 보트 하나에 탈 수 있는 인원은 최대 두명 이라는 조건을 보지 못했다.
  이걸 봤으면 그냥 바로 풀었을텐데...!
• 느낀 점. 문제를 정확히 봅시다.

1. 배열을 정렬하고,
2. 가장 가벼운 사람과 가장 무거운 사람을 짝지어 보트를 보낸다.

 

코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {

        int answer = 0;

        int leftIdx = 0; // 가장 가벼운 사람의 인덱스
        int rightIdx = people.length-1; // 가장 무거운 사람의 인덱스

        Arrays.sort(people);

        while(leftIdx<=rightIdx) {
            if(people[leftIdx] + people[rightIdx] <= limit) {
                leftIdx++;
                rightIdx--;
                    // 가장 가벼운 사람 + 가장 사람의 무게가 limit 이하이면
                    // 다음 가벼운 사람, 다음 무거운 사람의 인덱스로 재정의
            } else {
                rightIdx--;
                    // limit을 초과하면, 가장 무거운 사람만 보트에 태워보냄.
                    // 현재 가장 가벼운 사람은 다음 무거운 사람과 짝지어줘야하므로 -- 를 하지 않음.
            }
            answer++;
        }

        return answer;
    }
}

 

채점 결과

정확성  테스트
테스트 1 〉    통과 (1.94ms, 73.2MB)
테스트 2 〉    통과 (0.90ms, 74.1MB)
테스트 3 〉    통과 (1.74ms, 78.9MB)
테스트 4 〉    통과 (1.27ms, 74.3MB)
테스트 5 〉    통과 (0.93ms, 85.1MB)
테스트 6 〉    통과 (0.75ms, 76.4MB)
테스트 7 〉    통과 (1.15ms, 79.9MB)
테스트 8 〉    통과 (0.37ms, 72.1MB)
테스트 9 〉    통과 (0.53ms, 77.5MB)
테스트 10 〉    통과 (1.37ms, 81.7MB)
테스트 11 〉    통과 (1.88ms, 66.2MB)
테스트 12 〉    통과 (1.02ms, 79.5MB)
테스트 13 〉    통과 (1.10ms, 74.9MB)
테스트 14 〉    통과 (0.90ms, 73.4MB)
테스트 15 〉    통과 (0.45ms, 72.6MB)
테스트 16 〉    통과 (0.49ms, 76.6MB)
테스트 17 〉    통과 (0.38ms, 70.9MB)
테스트 18 〉    통과 (0.39ms, 86.4MB)
테스트 19 〉    통과 (0.34ms, 77.2MB)
테스트 20 〉    통과 (0.39ms, 76.3MB)
테스트 21 〉    통과 (0.37ms, 77MB)
테스트 22 〉    통과 (0.36ms, 70.8MB)

효율성  테스트
테스트 1 〉    통과 (21.33ms, 56.8MB)
테스트 2 〉    통과 (9.38ms, 55.4MB)
테스트 3 〉    통과 (16.10ms, 70.1MB)
테스트 4 〉    통과 (11.87ms, 56.5MB)
테스트 5 〉    통과 (18.37ms, 56.1MB)
채점 결과
정확성: 81.5
효율성: 18.5
합계: 100.0 / 100.0

 

 

 

좋은 풀이

0xrgb , hestarium , 한슬 , KING_SJ 외 6 명

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        for (; i < j; --j) {
            if (people[i] + people[j] <= limit)
                ++i;
        }
        return people.length - i;
    }
}

 

배운 점

1. for문을 해석해보자.
   • 만약 가장 가벼운 사람 + 가장 무거운 사람의 무게가 limit 이하이면 다음 가벼운 사람으로 넘어감
     => 즉, 보트에 무거운 사람 + 가벼운 사람을 태워서 보냄
   • 그렇지 않으면 다음 가벼운 사람으로 넘어가지 않음
     => 즉, 보트에 무거운 사람만 태워서 보냄
2. 이렇게 되면 i는 무거운 사람 + 가벼운 사람을 태워서 보낸 보트의 수가 된다.
3. 전체 사람의 수
   • = **무거운 사람**만 태워보낸 보트의 수 + **무거운 사람 + 가벼운 사람** 을 태워보낸 보트의 수 * 2 이다.
   • 전체 사람의 수 - **무거운 사람 + 가벼운 사람** 을 태워보낸 보트의 수
     = **무거운 사람**만 태워보낸 보트의 수 + **무거운 사람 + 가벼운 사람** 을 태워보낸 보트의 수
     = 보트의 총 개수
4. 그러므로 return people.length - i가 되는 것