[프로그래머스] 구명보트(투포인터_JAVA)

이틀 간 고민한 문제

알고리즘 분류가 greedy로 되어있어서,

한 가지 방법만 고민하다가

민성오빠의 힌트로 겨우 풀었다.

 

---

문제

 

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

프로그래머스

 

 

---

설계

 

 

알고리즘 설계[접근 방법] : 투포인터

이 경우는 투포인터로 풀었다.

처음에는 정렬 후 차례로 무게를 더한 후 초과하면 count를 세는 것으로 풀었는데, 제출하니 틀린 문제가 많았다.
그래서 힌트를 듣고 투포인터로 다시 풀었다.

첫 번째 풀이 : 잘못된 풀이

1. 사람들 무게를 오름차순으로 정렬한다.

2. 1부터 n까지 반복문을 돌며, 무게를 더한다.

3. 무게가 limit를 넘으면 answer+1한다.

: 만약 20, 20, 80, 80이고 limit가 100인 경우 정답은 2지만, 이 풀이로 풀면 4가 나오게 된다.

 

두 번째 풀이 : 투포인터

1. 사람들 무게를 오름차순으로 정렬한다

2. 마지막 n-1부터 0까지 반복문을 돌며 무게를 더한다.

3. idx라는 변수는 0부터 시작하며, 만약 limit-people[i]가 people[idx]보다 크면 이 둘을 더한다.

4. 즉, 현재 가장 무거운 사람을 구명보트에 태우고, 가장 가벼운 사람을 태울 수 있으면 태운다.

5. 두 사람의 무게가 limit를 초과한다면 무거운 사람만 태운다.

 

 

---

코드

 

[첫 번째 풀이]

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        //1. 무게 오름차순 정렬
        Arrays.sort(people);
        
        int sum=0;
        int count=0;
        for(int i=0; i<people.length; i++){
            sum+=people[i];
            count++;
            
            if(2<count || limit<sum) {
            	answer++;
            	sum=people[i];
                count=1;
            }
        }

        return answer;
    }
}

 

 

[두 번째 풀이]

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        //1. 무게 오름차순 정렬
        Arrays.sort(people);
        
        //가벼운 사람 인덱스
        int idx=0;
        
        
        for(int i=people.length-1; i>=0; i--){
            if(i<idx) break;
            
            //3. 현재 기준 가장 무거운 사람 태운 후 가장 가벼운 사람 태울 수 있으면 태운다
            if(people[idx]<=limit-people[i]) {
                answer++;
                idx++;
            }
            
            //5. 아니면 무거운 사람만 태운다.
            else answer++;
        }

        return answer;
    }
}

 

 

(❁´◡`❁)

끝!