[JAVA] 탐욕법(Greedy) "구명보트"

• int[] 에서 Integer[]로 변환하는 테크닉은 stream으로도 가능하지만, 효율성이 매우 떨어지므로 for문으로 하자.
• List도 필요할때만 사용하도록 하자. 이 역시 stream으로 Array를 asList를 이용하여 변환하능하지만 효율성이 매우 떨어진다.
• List의 remove와 같은 메소드는 동적으로 메모리를 사용하므로 효율성 측면에서 불리하다. 이왕이면 배열에서 index값을 이용하여 해결하자.
• 정렬 오름차순은 int[] Integer[] 다 가능하지만, 내림차순은 Integer[]만 가능하다(int[]는 Integer[]로 변환해야함)

=>내림차순 : Arrays.sort( 배열, Collections.reverseOrder());

 

 

나의코드 : 현실의 벽을 느꼈다.

import java.util.*;

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

            Integer[] p = new Integer[people.length];
            for(int i =0; i<p.length; i++){
                p[i] =people[i];
            }
            Arrays.sort(p, Collections.reverseOrder());

            int imax = p.length-1;
            int min = p[imax];
            int i=0;

            while(true){
                if(i==imax){
                    answer++;
                    break;
                }
                if(limit -p[i]<min){ //혼자 탈수밖에 없는 상황
                    i++;
                    answer++;
                }else{
                    if(p[i]+ p[imax]<= limit){//둘이서 탈경우
                        i++; imax--;answer++;
                        if(i>imax) break;
                    }else{//둘이서 못타는경우
                        i++;
                        answer++;
                    }
                }
            }
            return answer;
        }
    }

이 코드도 그렇게 긴 코드는 아니지만, 굳이 내림차순으로 생각한 것을 그대로 코드에 옮기다 보니, 길어졌다.

 

내림차순으로 정렬하여, 80 70 50 50인 경우, 80과 70은 첫번째 if문에서 걸러진다.

그리고 50은 else의 두번째 if문에서 걸러진다.

둘이서 못타는 경우를 또 다르게 정의한 것은 효율성 측면에서, 아예 min값으로 첫번째 if문에서 걸렀기때문이다.

그 보다 작은값들끼리 만났지만 못타는 경우를 처리하는 방식이다.

 

코드리뷰

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        for (; i < j; --j) {
            if (people[i] + people[j] <= limit)
                ++i;
        }
        return people.length - i;
    }
}

이 코드는 오름차순으로 정렬했을때의 처리방식이다.

작은 값부터 검사하여 작은값+가장큰값 <= limit 인경우에만 작은값의 index(i값)를 올려준다.

즉,

두개가 짝지어지면 i증가j감소하지만,

하나씩 짝지어질때는 j값만 감소한다.

 

이렇게해서 i값과 j값이 만나는 지점에서 break되고, 그 지점을 i라고 하자.

people.length -i = 최대인원수 - 두개씩 짝지어진 횟수(i가 카운터 역할)