[JAVA] Programmers <Greedy LV2> 구명보트

어릴 때 닌텐도 DS로 플레이했던 레이튼 박사 시리즈가 생각이 나는 문제...ㅋㅋ

아마 배열의 첫 인자부터 차례차례 남은 인자들과 합쳐서 limit를 넘는 순간 타고 빠지게끔? 작성하면 풀릴 거 같다.

---

package com.choonham;

class Solution {
	public int solution(int[] people, int limit) {
		int answer = 0;
		int sum = 0;
		int count = 0;

		for (int i = 0; i < people.length; i++) {
			if (people[i] != 0) {
				sum += people[i];
				people[i] = 0;
				if (i != people.length - 1) {
					for (int j = people.length - 1; j > i; j--) {
						if (people[j] <= limit - sum) {
							sum += people[j];
							people[j] = 0;
						}
					}
				}
				count++;
				sum = 0;
			}
		}
		answer = count;
		return answer;
	}
}

"스승님, 첫 시도에 이뤄지는 꿈을 꾸었어요..."

"근데 왜 울고 있는 것이냐?"

그 꿈은 어림도 없기 때문입니다...(으악!!)

 

이렇게 풀면 안되는 거 같다.

---

아마 가장 효율적인 경우를 찾는 방법이 아예 틀린 거 같다. 위 코드를 오름차순으로 정렬된 수에 대입하면 거의 100% 결과 값이 다르게 나온다. 또한 이중 for문은 이 문제가 원하는 답이 아닌 거 같다.

입력의 일관성을 위해 그럼 우선적으로 people배열을 정렬을 해줄 필요가 있다. 

또한 이중 for문을 사용하지 않는 대신에, 가장 큰 수(rifht)와 가장 작은 수(left)를 각각 더해서 limit와 비교하여 바깥쪽에서 안쪽으로 연산을 진행해주면, 최적의 해를 얻을 수 있을 거 같다. 

바로 해보자.

---

package com.choonham;

import java.util.Arrays;

class Solution {
	public int solution(int[] people, int limit) {
		int answer = 0;
		int count = 0;
		int sum = 0;
		Arrays.sort(people); //오름차순 정렬
		int right = people.length - 1;
		int left = 0;

		while (left < right) { //바깥쪽에서 안쪽으로
			sum = people[right] + people[left];
			if (limit < sum) { //한명만 타는 경우
				right--;
			} else {  //두명 이상 탈 수 있는 경우
				right--;
				left++;
			}
			count++; // 보트 출발
		}
		if (right == left) //가장 안쪽에 한명이 남았다면,
			count++; //태우고 출발

		answer = count;
		return answer;
	}
}

"스승님...."

"울지마라" 

 

결론: 나는 아직 멍청하다.