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

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

풀이

배열을 오름차순 정렬 -> 투 포인터로 보트 개수 카운트 한다

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);  // 사람들의 몸무게를 오름차순으로 정렬
        int left = 0;  // 가장 가벼운 사람을 가리키는 포인터
        int right = people.length - 1;  // 가장 무거운 사람을 가리키는 포인터
        int boats = 0;

        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                // 두 사람이 함께 탈 수 있는 경우
                left++;
                right--;
            } else {
                // 무거운 사람만 탈 수 있는 경우
                right--;
            }
            boats++;
        }

        return boats;
    }
}

해설

- 아이디어

- 최적화 코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);  // O(n log n) - 몸무게를 오름차순으로 정렬
        int left = 0;  // 가장 가벼운 사람의 인덱스
        int right = people.length - 1;  // 가장 무거운 사람의 인덱스
        int boats = 0;  // 필요한 보트의 수

        while (left <= right) {
            boats++;  // 보트를 하나 사용
            if (people[left] + people[right] <= limit) {
                left++;  // 가벼운 사람 태움
            }
            right--;  // 무거운 사람 태움 (두 경우 모두에서 무거운 사람은 항상 태움)
        }

        return boats;  // 최소 보트 수 반환
    }
}

- 시간복잡도와 텍스트공간복잡도

- 알고리즘 및 자료구조