[프로그래머스] Java - 구명보트

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

프로그래머스

Level 2. 구명보트

 

 

접근 방식
1. 사람들의 몸무게를 오름차순으로 정렬한다. 
2. 가장 무거운 사람부터 내려오면서, 가장 가벼운 사람과의 몸무게 합이 limit보다 적은 경우 한 보트에 넣는다.
   -- > 무거운 사람부터 내려와야 최대한으로 limit에 가깝게 보트에 태울 수 있기 때문이다.
3. 두 명의 합이 불가능한 몸무게는 한 명당 하나의 보트에 태운다. 

 

처음 코드

public static int Study(int[] people, int limit) {	
		int ans = 0;
		
		List<Integer> list = new ArrayList<>();
		for(int i : people) {
			list.add(i);
		}
		int min = list.get(0);
		
		if(min+list.get(1)>=limit)
			return list.size();
		
		//가장 가벼운 두명이 합이 limit 보다 클 때까지 반복
		while(min+list.get(1)<=limit)
		{
			//무거운 사람부터 아래로 내려오면서 가장 가벼운 사람과의 합이
			//limit보다 작은 경우를 찾는다.
			
			for(int i= list.size()-1; i>=1; i--) {
				if(min+list.get(i)<=limit) {
					list.remove(i);
					list.remove(0);
					ans++;
					break;
				}
			}
			min = list.get(0);
		}
		ans+= list.size();
		System.out.println(ans);
		
		return ans;
	}

처음에는 이렇게 코드를 짰는데 정확도는 100퍼센트였으나, 효율성에서 3개가 시간초과가 되었다.

아무래도 반복문을 두번 돌다 보니 효율성이 떨어질 수 밖에 없을 것 같았다. 그것을 보완하여 다시 코드를 짜보았다. 

 

 

최종 코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
       int ans = 0;
		
		Arrays.sort(people);
		
		int max = people.length-1; //가장 큰 인덱스
		int min = 0; //가장 작은 인덱스
		
        //인덱스 비교
		while(min<=max) {
     	   //두 개의 합이 limit보다 작으면 한 보트에
			if(people[min]+people[max]<=limit) {
				min++;
			}
			ans++;
			max--;
			
		}
		
		return ans;
    }
}

 

 

고찰

알고리즘에서는 가장 큰 인덱스부터 차례로 내려오는 점이 중요한 것 같다. 만약 작은 인덱스부터 올라갔다면, limit에 더 가깝게 태울 수 있는 부분을 확인하지 못하였을 것이다. 

 

사실 탐욕적 방법같은 알고리즘을 많이 접하지 못해서, 지레 겁먹고 시작했는데 생각 외로 잘 풀려서 놀랐다.

또, 효율성 면에서도 어떤 점이 문제인지 찾아내고 해결방안까지 찾을 수 있는 내 모습에 나도 놀랐다...

간단한 문제였지만 배울게 많은 문제였던 것 같다.