문제

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

나의 풀이

• {50, 50, 70, 80} 로 정렬, limit 100, result = 3
• 차례대로 빼주고 뺀 값이 0보다 작아지면 while문을 탈출하고 answer++
• 테스트 케이스는 통과했지만 정답은 아니었다.
• 최대 2명만 태울 수 있다는 요구사항도 제대로 보지않았다.(바보!)

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

        Arrays.sort(people);
        Stack<Integer> st = new Stack<>();
        for (int i = 0; i < people.length; i++) {
            st.add(people[i]);
        }

        while (!st.isEmpty()) {
            int sum = limit;
            while (sum > 0 && !st.isEmpty()) {
                if ((sum -= st.peek()) >= 0) {
                    st.pop();
                }
            }
            answer++;
        }
        return answer;
    }
}

<반례> 
{30, 40, 50, 60}, 100, 2
뒤에서부터 빼주면 result = 3 이 나온다. 
실제로는 (30 + 60), (40 + 50) 으로 2번만으로도 충분하다.

다른 풀이

• 순서대로 정렬 후 가장 작은 수와 가장 큰 수의 합이 limit을 넘지않으면 둘다 아웃
• 가장 작은 수와 가장 큰 수의 합이 limit을 넘으면 가장 큰 수만 아웃
• 가장 작은 수와 가장 큰 수의 index가 같아지면 answer++ 해주고 종료

import java.util.Arrays;

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

        Arrays.sort(people);
        int start = 0;
        int last = people.length - 1;

        while (start < last) {
            if (people[start] + people[last] <= limit) {
                start++;
                last--;
            } else {
                last--;
            }
            answer++;
        }
        
        if (start == last) {
            answer++;
        }
        return answer;
    }
}

어나더 풀이

import java.util.Arrays;

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