프로그래머스. 구명보트 (자바)

[문제 설명]

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

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

[제한사항]

무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

[입출력 예]

people limit return
[70, 50, 80, 50] 100 3
[70, 80, 50] 100 3

---

[문제 풀이 과정]

가장 무거운 사람 순서대로 보트에 넣어야 한다고 생각했다.
모두 보트에 타야하긴 하니 제일 무거운 순서대로 나눌 필요가 없을것 같기도??
그럼 70, 50, 80, 50 몸무게가 주어졌을때 어차피 모두가 보트에 타야하긴 하니까 제일 첫번째 사람을 일단 limit 100짜리 보트에 집어넣는다. 그리고 두번째 사람을 집어넣어. 그런데 그 무게가 리밋을 넘으면 빼. 그리고 그 다음 사람을 집어넣어. 그 무게가 리밋을 넘으면 빼. 그리고 만약 그 다음 사람을 넣었는데 무게가 리밋을 안 넘는다? 그럼 냅둬!!
근데 이 과정으로 하면 너무 비효율적일 것 같고,
만약 인덱스 0번째의 사람과 3번째의 사람을 한 보트에 태웠다면 이제 그 둘은 빼고
나머지 가지고 계산해야 하는건데 그 3번째 사람 빼는 일이 조금 복잡하게 느껴진다.

그래서 그냥 무게순으로 배열 정리 하기로 하자.
List<String> list = Arrays.asList(arr); 를 이용해서
Collections.sort(list, Collections.reverseOrder());를 이용해서 배열의 숫자를 내림차순으로 정렬하자!! 

그런데 무게순으로 정리하고 나서 그럼 0번째 1번째 보트에 태우고 안되면 0번째만 태우고
1번째 2번째 보트에 태우고 이렇게 해야되나? 그러니까 최대한 무거운 사람들끼리 짝짓는 순서로??
아니아니!!!!! 그러면 80과 70을 넣으면 리밋을 넘지만 80과 50을 넣으면 리밋을 안 넘어서
짝지을 수 있는 경우를 고려 못 하게 되버린다!!

그래서 무게순으로 나열한 뒤 가장 무거운 사람과 가장 가벼운 사람을 짝지어서
리밋 안 넘으면 둘이 태우고 넘으면 가장 무거운 사람만 태우고 이제 걔빼고
나머지 사람들로 반복하는 식으로 풀기로 했다.
근데 만약 제일 무거운 사람과 2번째 가벼운 사람을 넣어도 limit을 안 넘으면?? 또는 제일 무거운 사람과 4번째 가벼운 사람을 넣어도 limit을 안 넘으면?? 그럴때는 limit에 가까운 무게를 최대한 채우는게 낫지 않나 싶었지만 어차피 보트에는 2명씩밖에 못 타기 때문에 둘은 똑같은 상황이다. 만약 한 보트에 여러명씩 탈 수 있다면 최대한 무거운 애들끼리 짝짓고 나머지 가벼운 애들끼리 몰아넣으면 되는데 한 보트에 2명씩 밖에 못 타니까 그 상황은 가정하지 않아도 되는것!!!

다시 정리하면
내림차순으로 정렬하고 제일 무거운 사람과 제일 가벼운 사람을 보트에 넣은 뒤 limit을 안 넘으면 둘이 태우면 되고! 만약 limit을 넘으면 제일 무거운 사람만 태우고 이제 다음 시행을 하는 식으로 반복하면 된다. 
46분 18초
1. 리스트를 arraylist로 바꾸기
2. collection 이용해서 내림차순으로 정렬하기
3. arraylist.get[0]과 arraylist.get[n]을 더한게 limit 보다 작으면 둘을 한 보트에 넣기. 보트 갯수를 0으로 놓은 다음에 보트 쓸 때마다 +1씩 해주면 됨
4. 만약 둘이 더한게 limit보다 크면 무거운 애만 넣고 걔는 이제 없는애 취급하기
5. 그럼 이제 그 다음 무거운 애부터 똑같이 반복하면 됨.

그런데 막히는 부분 : 
그럼 한번 시행마다 배열의 맨 앞에 있는 애는 무조건 보트에 들어가겠지만
배열의 맨 뒤에 있는 애는 리밋을 안 넘으면 들어가는 거고 넘으면 안 들어가는건데
시행마다 마지막 애를 넣을지 안 넣을지 그걸 구분하고 다음 시행에는 맨 마지막 애가 바뀌었는지 안 바뀌었는지를
어떻게 기록하지??? 흐으응으응믐ㅁ.... 너무 어렵땅...

참고 블로그 (그리디 알고리즘)

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

 

A FEW DAYS LATER....

 

새로운 테스트 케이스로 생각해보기

만약 몸무게가 80, 70, 60, 50, 50, 30 이렇게 주어진다면? (몸무게 내림차순으로 정렬한 다음을 가정)
80 혼자, 70 +30, 60 혼자, 50+50 이렇게 보트를 타서 최소 4개가 필요할 것이다. 저 숫자들을 arr 배열에 넣었다고 할때
arr[0] + arr[arr.length-1]  >  100 -> arr[0]만
arr[1] + arr[arr.length-1] <= 100 -> arr[1]과 arr[arr.length-1] 함께
arr[2] + arr[arr.length-2]  >  100 -> arr[2]만
arr[3] + arr[arr.length-2] <= 100 -> arr[3]과 arr[arr.length-2] 함께
이렇게 해서 총 4개인 것이다.
앞에 인덱스는 0부터 시작해서 1씩 늘어나므로 쟤를 기준으로 반복문 돌리면 되고
뒤에 인덱스는 arr.length-1부터 시작해서 만약 합이 100보다 크면 그냥 유지하고
만약 합이 100 이하면 보트 갯수 1추가 하고 인덱스는 1 줄어드는 방식으로 한다.
그럼 반복문이 언제 끝인걸 깨닫지?
앞 숫자의 인덱스가 뒷 숫자의 인덱스보다 크거나 같으면 끝난것!! 이대로 한번 코드를 짜보자.

근데 배열 내림차순할 때 
Arrays.sort(people, Collections.reverseOrder()); 를 쓰면 되긴 하는데 문제는
배열 선언할 때 Integer people[] = {70, 50, 80, 50} 이런식으로 해야된다는 것임.
프로그래머스 함수에 매개변수로 int[] people 이렇게 되어 있는데 우째??;;;
이건 나중에 해결하고, 일단 코드를 짜보자!

 

[처음으로 패스받은 코드]

import java.util.Arrays;
import java.util.Collections;

public class Main {
	public static void main(String[] args) {
		
		int people[] = {70, 80, 50, 60, 50, 30};
		// collections 함수를 사용하려면 int 안되고 Integer여야함
		
		Integer weight[] = Arrays.stream(people).boxed().toArray(Integer[]::new);
		// 그래서 int배열을 Integer 배열로 바꾸기
		
		int limit = 100;
		// 보트 하나당 무게 제한
		
		int boatNum = 0;
		// 구명보트 갯수 0으로 시작
		
		Arrays.sort(weight, Collections.reverseOrder());
		// 몸무게 내림차순으로 재배열
		
		System.out.println("몸무게순으로 내림차순한 배열 : " + Arrays.toString(weight));
		
		int end = weight.length - 1;
		// 몸무게 제일 작은애 인덱스
		
		for(int start = 0 ; start < weight.length ; start++) {
			
			if(weight[start] + weight[end] <= limit) {
				boatNum++;
				end--;
				// 제일 무거운애랑 제일 가벼운애 더해서 리밋 안 넘으면
				// 보트에 넣고 맨 뒤 인덱스도 한칸 앞으로
			} else {
				boatNum++;
				// 근데 만약 둘이 더해서 리밋 넘으면
				// 맨 뒤 인덱스 유지. 맨 앞 인덱스는 반복문 때문에 자동 증가
			}
			
			if(start >= end) {
				break;
				// 앞의 인덱스가 뒤의 인덱스보다 크거나 같으면 보트에 다 탄 것
			}
		}
		System.out.println(boatNum);
  }
}

오오오오!!! 패스했다!!! 머릿속으로 제일 가벼운 애를 어쩔 때는 보트에 넣고 어쩔 때는 안 넣는데 걔 인덱스를 어떻게 계산할지 생각만 하다가 노트에 직접 인덱스로 정리하니 어떻게 반복문을 짜야할지 보였다!!