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

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42885

코딩테스트 연습 - 구명보트 | 프로그래머스

코드

package Programmers.Level2;

import java.util.Arrays;

public class LifeBoat {

	public static void main(String[] args) {

		int[] people = {
				25,25,25,25
		};

		int limit = 50 ;

		int answer = solution(people,limit);

		System.out.println(answer);


	}

	public static int solution(int[] people, int limit) {

		int answer = 0;

		Arrays.sort(people);

		// 최적은 가장 가벼운사람 + 가장 무거운사람을 먼저보내는것이다.
		int i = people.length-1;
		int j = 0 ;
		
		while ( i > j ) {
			
			if( people[i] + people[j] <= limit ) j++;
			
			i--;
			
			answer++;
		}
		
		if ( i==j ) answer++;
		
		return answer;
	}
}

나의 풀이

문제의 핵심은 한번에 최대2명씩 탈 수 있다는 것이다.

 

이때 가장 큰 효율을 낼 수 있는 방법은 [ 가장 무거운사람 + 가장 가벼운사람 ] 을 먼저 태워보내는것이다.

 

결과적으로, 가장 무거운사람부터 보트에 태워서보내는데 추가로 가벼운 사람을 태울 수 있으면 같이 태워 보내도록 하였다.

 

i = 가장 큰 수부터 ( people.length-1 )

j = 0 부터 

 

i > j 까지 ( 어긋날 때 까지 )

 

1,1,3,3,4 / limit는 4인경우

 

1회전 ==> 4혼자 보낸다 ==> i-- ;

 

2회전 ==> 3,1 같이 보낸다 ==> i-- , j++ ;

 

...

 

추가로 10,10,30,15 / 25 와 같은경우에

 

i = 3 , j = 0 부터 시작해서

 

1회전 ==> 10,15 보냄 ==> i=2, j=1

2회전 ==> 30 보냄  ==> i=1 , j=1

 

하게되면 첫번째 index인 10을 처리하지못하는 경우가 발생한다.

 

그래서 마지막에 i==j로 종료 된 경우는 결과 값을 +1해준다.

제출 결과