<알고리즘 Q1 - Greedy> 짐 나르기 // 답변 외움.

 

 

 

 

 

==================해답========================

 

public class Solution { 

  public int movingStuff(int[] stuff, int limit) {

    // TODO:

    /*

    박스에 최대 2개의 짐밖에 못넣음.

    최대한 적게 사용하여 짐을 옮기기 위함.

    <참고사항>

    짐의 무게를 담은 배열 stuff, 박스 무게 제한 limit

    필요한 박스 개수의 최소값을 return.

    <접근방법>

    1. for문으로 stuff 배열을 정리

    2. stuff 요소들 2개의 합이 limit 이하여야함.

    3. stuff.length는 가장 많은 박스의 사용 수.

    4. 박스의 최소값 = stuff.length - (stuff[i] + stuff[j] <= limit의 숫자)

    <주의사항>

    1<= stuff.length <= 50000

    */

    // 배열 요소를 크기별로 나열.

    Arrays.sort(stuff);

    // 최소한의 횟수 min 초기화.

    int min = 0;

    // 2개씩 나를 수 있는 경우를 할당할 변수.

    int box = 0;

    

    // 크기대로 정렬한 stuff의 가장 좌측 인덱스

    int left = 0;

    // 크기대로 정렬한 stuff의 가장 우측 인덱스

    int right = stuff.length-1;

    // 조건문 (우측이 좌측보다 클 경우에만)

    while(left < right) {

      // 가장 가벼운 물건 + 가장 무거운 물건 <= limit

      if (stuff[left]+stuff[right]<=limit) {

        // 위의 조건이 해당할 경우, left는 다음으로 큰 인덱스, right는 다음으로 작은 인덱스 할당

        left++;

        right--;

        // 2개씩 한번에 옮길 수 있는 경우의 변수 box이므로 1씩 증가.

        box++;

      }

      // 위의 조건이 아닐 경우에는 가장 무거운 물건 하나만 나르는 경우이므로, 우측 인덱스 1씩 감소

      else {

        right--;

      }

    }

    // 박스의 가장 적은 사용 빈도 = 총 물건의 양(각자 1개씩만 나를 경우) - 2개씪 나르는 경우.

    min = stuff.length-box;

    return min;

  } 

}