99클럽 코테 스터디 17일차 TIL + Greedy(구명보트)

오늘의 과제

프로그래머스 Lv.2로 분류된 구명보트입니다.

 

이번 문제 유형은 어제에 이어 순차적으로 최선의 선택을 이어나가는 탐욕법(Greedy)입니다.

문제

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

프로그래머스

 

 

먼저 문제 요구사항 요약입니다.

 

각 사람의 무게와 구명 보트의 한계 중량이 주어집니다.

 

최대한 잘 분배하여 최소한의 구명 보트로 모든 사람을 구하는 문제입니다.

 

그리디라는 문제 분류에 걸맞게 계산하기 쉬운 무거운 사람들부터 구명 보트에 태웠습니다.

 

주어진 사람들 몸무게 배열에서 쉽게 계산하기 위해 오름차순 정렬 후

이분 탐색을 통해 진행하면 됩니다.

 

정렬을 진행했으니 0번 인덱스는 제일 가벼운 사람이 될테고,

length - 1 인덱스는 제일 무거운 사람이 됩니다.

 

왼쪽 커서를 뜻하는 lt와 오른쪽 커서를 뜻하는 rt를 통해 사람을 태울 때마다

lt++ 혹은 rt--를 통해 모두 태워보면 됩니다.

 

다만 문제의 조건에 맞게 2명을 초과하여 태웠는지,

구명 보트의 한계 중량은 넘지 않았는지 매 반복문마다 확인합니다.

 

 

코드입니다.

import java.util.*;

class Solution {
    public static int solution(int[] people, int limit) {
        int answer = 0;
        int lt = 0, rt = people.length - 1;
        Arrays.sort(people);

        for (int i = 0; i < people.length; i++) {
            int cnt = 0, sum = 0;

            // 무거운 사람들 먼저 태워본다.
            while(rt >= lt) {
                if ((sum + people[rt]) > limit) break;
                if (cnt >= 2) break;
                sum += people[rt--];
                cnt++;
            }
            // 남은 공간에 가벼운 사람들을 태워본다.
            while(lt < rt) {
                if ((sum + people[lt]) > limit) break;
                if (cnt >= 2) break;
                sum += people[lt++];
                cnt++;
            }
            
            if (cnt == 0) break;
            answer++;
        }
        return answer;
    }
}

// people 오름차순 정렬
// lt = 가벼운 순, rt = 무거운 순
// rt를 먼저 채우고 무게 초과시 lt를 최대한 채운다.

 

배운 점

예전 학습 때 배운 이분 탐색을 활용하였습니다.

 

당연히 바로 떠올리진 못했고 정렬 후 무거운 사람의 인덱스, 가벼운 사람의 인덱스를 쉽게 체크하며

사람들을 태워볼 방법을 찾다가 이분 탐색을 발견했습니다.

 

문제 풀이를 2주 좀 넘게 진행하며 새롭게 알게된 지식과 자주 쓰이는 기법들이 떠오르고 있는데

게시글 내 별도 카테고리로 만들어 한 번 정리할 필요성을 느끼고 있습니다.

 

 

오늘의 한줄평

기록하지 않고 사용되지 않는 기억은 저 멀리 무의식속으로 ...