구명보트_복습2

2026.09.23

문제 풀이

1차 실행 오류

---

81.5/100.0

효율성 테스트 시간 초과

---

시간 초과 원인 분석

---

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int boat = 0;
        Arrays.sort(people);
        
        for (int i = 0; i < people.length; i++) {
            int tail = people.length - 1;
            while(true) {
                if (i > tail) {
                    break;
                }
                if (people[i] + people[tail] <= limit && people[tail] != -1) {
                    people[i] = -1;
                    people[tail] = -1;
                    boat++;
                    break;
                }
                tail--;
            }
        }
        for (int i = 0; i < people.length; i++) {
            if (people[i] != -1) {
                boat++;
            }
        }
        return boat;
    }
}

나의 코드

---

소요 시간: 30분
시간 복잡도: $O(nlogn)$

---

import java.util.Arrays;

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

AI 코드

---

시간 복잡도: $O(nlogn)$

---

코드 분석

전체적인 구조는 동일하며, 조건문 작성 정도의 차이가 있다.

---

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int boat = 0;
        int left = 0, right = people.length - 1;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;   // 가벼운 사람도 함께 탑승
            }
            right--;      // 무거운 사람은 무조건 탑승
            boat++;
        }
        return boat;
    }
}

문제 풀이 후기

2번이나 실패했던 문제를 해결하니 속이 뻥 뚫리는 듯한 느낌이다.
코드를 작성하면서 이전에 어디에서 애를 먹었는지 알 것 같았고,

해당 부분을 해결하니 확실히 체감이 크게 되진 않지만
실력이 늘고 있다는 것을 느낄 수 있었다.