[Programmers/Java]프로그래머스 연습문제 - 구명보트 (그리디 Greedy 알고리즘)

문제링크

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

프로그래머스

문제조건

.

풀이(성공)

일단 이 문제는 Greedy (탐욕 알고리즘)을 이용해서 풀어야 하는 것 같았다.

나는 탐욕법에 대하여 전혀 모르고 있기 때문에.. 이를 이해하기 위해 검색을 실시했다.

탐욕 알고리즘(Greedy)이란, 무언가를 선택해야할때(탐색해야할때) 눈 앞의 최적의 상황만 찾아서 답을 찾는 방법이다.

문제 해결 방법은 다음과 같다.

1. 선택 - 현재 상태에서 최적의 해답을 선택

2. 적합성 검사 - 선택된 해가 문제의 조건을 만족하는지 검사

3. 정답 검사 - 1,2 를 거친 해답으로 문제가 해결되었는지 확인 후 해결되지 않았다면 1,2의 절차로 돌아가서 위의 과정을 반복

 

나는, 최소+최대값을 limit에 들어가는지 확인하고 들어가면 2개의 숫자를 array에서 없애고 count를 +1, 안들어갈경우 최대값만 없애고 count를 +1하는 방식으로 작성했다. 

 

작성코드(성공)

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
                int answer = 0;
        //정렬 후 최솟값 + 최댓값이 limit 안에 들으면 같이가고 , 아니면 최댓값을 그 다음으로 큰 값으로 변경
        Arrays.sort(people);
        int maxIndex=people.length-1;
        int max=people[maxIndex];
        int minIndex=0;
        int min=people[minIndex];
        while(true){
            max=people[maxIndex];
            min=people[minIndex];
           // System.out.println("maxIndex = "+maxIndex+", minIndex = "+minIndex+", answer = "+answer);
            if(minIndex==maxIndex){
                answer++;
                break;
            } else if (minIndex>maxIndex) {
                break;
            }
            //System.out.println("min+max = "+(min+max));
            if(min+max<=limit){
                answer++;
                minIndex++;
                maxIndex--;

            }else{
                answer++;
                maxIndex--;
            }
        }
        return answer;
    }
}

.