문제 접근

일단 정렬시키고, 가벼운 사람부터 난 기준을 삼았다. 가벼운 사람은 가장 무거운 사람부터 시작해서 자기가 함께 탈 수 있는 무거운 사람들과 순차적으로 보트를 태워보낸다.

• 이때, 무게에 대한 정보와 각 무게별 남은 인원의 정보는 별도로 관리했다.
• 이로인해, 정렬 시간 및 탐색 시간이 줄어들 수 있다.

=> 만약 자신보다 무거운 사람들과 함께 다 탔고, 무게가 같은 사람들만 남았다면, 둘이 탈수 있는지 확인하고 가능한 둘이 묶어서 태워 보낸다.

                    if(i*2 <= limit){
                        answer += (remainSize[i]/2 + remainSize[i]%2);
                        remainSize[i] = 0;
                    }

풀이

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int[] remainSize = new int[241];
        ArrayList<Integer> weights = new ArrayList();
        for(int p : people) {
            if (remainSize[p]==0) {
                weights.add(p);
            }
            remainSize[p]++;
        }
        Collections.sort(weights);

        int i = weights.get(0);

        while(i<=weights.get(weights.size()-1)) {
            if(remainSize[i] == 0) {
                i++;
                continue;
            } 
            
            for(int j=limit-i; j>=i; j--) {
                if(remainSize[j] == 0) continue;
                if (i != j) {
                    int reduceSize = Math.min(remainSize[i], remainSize[j]);
                    remainSize[i] -= reduceSize;
                    remainSize[j] -= reduceSize;
                    answer+=reduceSize;
                    if (remainSize[i] == 0) break;
                } else {
                    if(i*2 <= limit){
                        answer += (remainSize[i]/2 + remainSize[i]%2);
                        remainSize[i] = 0;
                    }
                }
            }
            
            if (remainSize[i] == 0) continue;
            
            answer+=remainSize[i];
            remainSize[i] = 0;
        }
        
        return answer;
    }
}

그리디가 약하다고 판단해서 계속 연습 중이다.. 다음주는 구현 연습을 해야겠다.

문제를 다시 풀어보았다. - 24년 5월 22일

그냥 투포인터로 풀면 되는건데, 나는 무슨 짓을 했던걸까.... 코드가 확짧아져서 기분이 좋다.

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int i = 0; 
        int j = people.length - 1;
        while(i<j) {
            if (people[j] + people[i] <= limit) {
                answer++;
                i++; j--;
            } else {
                answer++;
                j--;
            }
        }
        if (i==j) answer++;
        return answer;
    }
}