<Algorithm> 구명보트

kukjunLEE·2022년 4월 12일
1

Algorithm

목록 보기
2/2

구명보트 문제 링크

문제 요약

무인도에 갖힌 사람들을 구명보트를 이용해 구출하려고 한다.

구명 보트는 최대 두명씩 한번에 옮길 수 있다.
구명 보트는 가장 적게 사용해야 한다.
구명 보트의 무게 제한은 40kg ~ 240kg 이다.
각 사람의 몸무게는 40kg ~ 240kg 이다.
구명 보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없다.

사람들의 몸무게를 담은 배열 people과 구명 보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트의 개수의 최솟값을 return 하도록 solution 함수를 작성해라

풀이 방법

O(n) 풀이 방법

개수를 세는 방법(1)

40~240 으로 범위를 지정해주므로, 해당 범위의 값들을 배열을 이용해서 숫자를 세고, 배열에 저장한 값들 중에서 보트를 만들 수 있는 조건이 있으면 해당하는 사람을 빼서 해결하는 방식.

public class Solution {

    static public int solution(int[] people, int limit) {
        int[] array = new int[241];
        for (int i = 0; i < people.length; i++) {
            array[people[i]]++;
        }
        int answer = 0;
        int person = people.length;
        int nowPoint = 240;

        while (person != 0) {
            if (array[nowPoint] == 0) {
                nowPoint--;
                continue;
            }

            person--;
            array[nowPoint]--;

            answer++;

            for (int i = 240; i >= 40; i--) {
                if (array[i] != 0) {
                    if (i + nowPoint <= limit){
                        person--;
                        array[i]--;
                        break;
                    }
                }
            }

        }

        return answer;
    }
}
  • while(person != 0) 으로 인해서 O(n) 시간 복잡도를 가진다.

O(1) 풀이 방법

개수를 세는 방법(2)

40~240으로 범위를 지정해주고, 해당 범위의 값들을 배열을 이용해서 숫자를 세고, 배열에 저장한 값들의 개수를 이용해서 최대 횟수를 240*240 의 연산방식을 적용하는 방식.

package programmers;

class Solution {
    public int solution(int[] people, int limit) {

        int[] array = new int[241];

        // 인덱스 값에 넣기
        for (int i = 0; i < people.length; i++) {
            array[people[i]]++;
        }

        int answer = 0;
        int firstPoint = limit;
        int secondPoint = 0;

        // 경우 판단하기
        while (firstPoint >= 40) {
            // 해당 배열의 개수가 0개라면
            if (array[firstPoint] == 0) {
                firstPoint--;
                continue;
            }

            // limit + 40보다 더 큰 경우라면
            if (limit - firstPoint < 40) {
                answer += array[firstPoint];
                array[firstPoint] = 0;
                firstPoint--;
                continue;
            }

            // 두번째 탈 사람을 정하기 위함
            // 만약 limit 의 절반 값보다 크다면
            if (limit < firstPoint * 2) {
                // 두번째 사람은 최대 무게 - 첫번째 탄 사람 무게보다 작아야 한다.
                secondPoint = limit - firstPoint;
            }
            // 만약 limit 의 절반 값보다 작다면
            else {
                // 해당하는 값 두개씩 묶어서 값에다 더함.
                if (array[firstPoint] % 2 == 0) {
                    answer += array[firstPoint] / 2;
                    array[firstPoint] = 0;
                    firstPoint--;
                    continue;
                } else {
                    answer += array[firstPoint] / 2;
                    array[firstPoint] = 1;
                    secondPoint = firstPoint - 1;
                }
            }

            while (secondPoint >= 40) {
                if (array[secondPoint] == 0) {
                    secondPoint--;
                    continue;
                }

                // if 문이 필요한가?
                if (array[firstPoint] > array[secondPoint]) {
                    answer += array[secondPoint];
                    array[firstPoint] -= array[secondPoint];
                    array[secondPoint] = 0;
                    secondPoint--;
                } else if (array[firstPoint] < array[secondPoint]) {
                    answer += array[firstPoint];
                    array[secondPoint] -= array[firstPoint];
                    array[firstPoint] = 0;
                    break;
                } else {
                    answer += array[firstPoint];
                    array[firstPoint] = 0;
                    array[secondPoint] = 0;
                    break;
                }

            }

            // secondPoint 을 다 찾아봐도 없다면, 해당하는 배열로 믂어서 더함.
            if (array[firstPoint] != 0) {
                answer += array[firstPoint];
                array[firstPoint] = 0;
            }
            firstPoint--;

        }
        return answer;
    }
}
  • 상수 while문으로 인해서, O(1) 시간 복잡도를 가진다.

시간 복잡도에서 큰 이득을 얻을 수 있다.

profile
Backend Developer

0개의 댓글