[Programmers/Lv2) 구명보트 - Java

알고리즘 문제 풀이 / 프로그래머스 (programmers)  - 구명보트

 

 

 

문제 링크

 

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

코딩테스트 연습 - 구명보트

 

 

문제 풀이

 

배열 people을 정렬시킨다.

hap 이 limit을 넘어간다면 i-- 해준다.

마지막 남은 값이 하나라면 answer++

 

 

 

구명보트를 최대한 적게 사용해야 하므로 가장 무거운 사람부터 고려하면 되는 문제이므로 바로 오름차순 정렬을 했다. 내림차순으로 해도 되고 상관없는데 난 그냥 오름차순으로 했다. hap에 마지막 무게를 넣어둔 후 가장 가벼운 사람을 더했을 때 limit 초과라면 가장 가벼운 사람은 탑승하지 못하므로 변수 i를 다시 감소시킨다. 이런 식으로 풀었을 때 마지막에 한 사람만 남게 된다면 answer 값 하나를 증가시켜주면 된다.

 처음에 문제를 제대로 읽지 않아 한 번에 2명만 탈 수 있단 것을 모른 채로 풀었다. 분명히 맞게 풀었는데 실패를 해서 대체 뭘까 하고 문제를 다시 읽어보니 맨 첫 줄에 2명이란 제한이 있었다. 문제를 꼼꼼히 읽는 습관을 들이도록 더 노력해야겠다. 

 

public static int solution(int[] people, int limit) {
	int answer = 0;
	Arrays.sort(people);
	int last = people.length-1;
	int hap = people[last];

	for(int i = 0; i <= last; i++) {
		hap += people[i];
        
		if(hap > limit) i--;
		
		last--;
		hap = people[last];
		answer++;
        
		if(i+1 == last) {
			answer++;
			break;
		}
	}
	return answer;
}