🔗 링크

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

🛶 문제

두 명씩 옮길 수 있는 구명보트가 있다.

구명보트는 무게에 한계가 있고, (limit)

사람들을 옮기는 최소한의 횟수를 구해야한다.

👀 예제로 문제 파악하기

입력 : people [70, 50, 80, 50], limit 100

최소한의 횟수로 옮기기 위해서는 가장 몸무게가 큰 사람 + 가장 몸무게가 작은 사람 조합이여야 한다.

위 예제같은 경우에는

1. 80 (최솟값인 50과 같이 가면 한계점인 100을 넘는다.)
2. 70 (최솟값인 50과 같이 가면 한계점인 100을 넘는다.)
3. 50 + 50

순으로, 총 횟수인 3을 return한다.

---

입력 : people 50, 30, 20, 70, 10, limit 100

1. 70 + 10
2. 50 + 20
3. 30

😮 알고리즘 풀이 순서

max는 정렬된 배열의 맨 끝에서, min은 맨 처음에서 시작.

max + min이 limit을 넘으면 혼자 가는 것으로, 넘지 않으면 두 개가 함께 가는 것으로 처리

50 + 80은 limit인 100을 넘으니 80 혼자 간다.

50 + 70도 마찬가지

50 + 50은 limit인 100과 같으므로 둘이 갈 수 있음

둘이 간다는 차리를 하기 위해 min을 1 누적해준다.

---

1. 배열 people을 정렬한다.

2. min은 0으로 초기화해준다.

   • 최솟값의 위치의 역할

3. 반복문을 돈다.

   • 초기값 max는 people 배열의 크기 -1
     - max는 최댓값 위치의 역할
   • min ≤ max일 때까지 반복
     - 최솟값의 위치가 최댓값의 위치보다 커지면 반복 종료
   • max—

4. 반복문

   • people의 min 위치에 있는 값 + max 위치에 있는 값이 limit보다 작거나 같으면 min++.
   • answer++
     - 위 if문에서 걸리지 않으면 현재 최댓값 혼자 구명보트를 탄 걸로 처리

👨‍💻 코드

public class Solution {

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

    Arrays.sort(people);

    int min = 0;

    for (int max = people.length - 1; min <= max; max--){
      if (people[min] + people[max] <= limit) min++;
      answer++;
    }

    return answer;
}

  @Test
  public void 정답() {
    Assert.assertEquals(1, solution(new int[]{50}, 50));
    Assert.assertEquals(2, solution(new int[]{20, 50, 50, 80}, 100));
    Assert.assertEquals(3, solution(new int[]{70, 50, 80, 50}, 100));
    Assert.assertEquals(3, solution(new int[]{50, 30, 20, 70, 10}, 100));
    Assert.assertEquals(3, solution(new int[]{70, 80, 50}, 100));
    Assert.assertEquals(5, solution(new int[]{10, 20, 30, 40, 50, 60, 70, 80, 90}, 100));
  }
}