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

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

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

import java.util.Arrays; 
class Solution {
	    public int solution(int[] people, int limit) {
	        int answer = 0;
	        int left=0;
	        int right=people.length-1;
	        Arrays.sort(people);
	        
	        while(left<=right) {
	        	
	        	if(people[right]+people[left]<=limit) { //가벼운사람 + 무거운사람 가능 
	        		right--;
	        		left++;
	        		answer++;
	        	}
	        	else { // 둘이 같이 못타면 무거운 사람만 태움
	        		right--;
	        		answer++;
	        	}
	        }
	        
	        return answer;
	    }
	}

소요시간 : 10분

 

매우 간단한 문제입니다. n이 50000이기 때문에 n^2은 시간초과입니다!

그래서 그리디, 이분탐색인데 그리디인거 같아서 그리디로 풀었습니다!

 

여러명의 사람이 있을 때 가장 최소로 구명보트를 쓰는법은 간단합니다.

가장 무거운 사람 + 가장 가벼운 사람을 같이 구명보트에 태우는 방법을 사용하면 됩니다.

 

로직을 살펴보면

 

1. 몸무게를 오름차순으로 정렬

2. 가장 무거운 사람과 가장 가벼운 사람의 몸무게를 더했을 때 limit보다 작다면 구명보트 하나 추가

   -  left++, right-- 를 해서 인덱스를 옮겨줍니다.

3. 가장 무거운 사람과 가장 가벼운 사람의 몸무게를 더했을 때 limit보다 크면 구명보트하나 추가

   - 가장 무거운 사람만 구명보트에 타기 때문에 right--만 해줍니다.

 

끝~