[Algorithm] 모험가 길드

문제

한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 공포도를 측정했다.

공포도가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.

공포도가 X인 모험가는 반드시 X명 이상으로 구성된 모험가 그룹에 참여해야 여행을 떠날 수 있다.

최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다.

 

입력 조건

첫째 줄에 모험가의 수 N

둘째 줄에 모험가의 공포도 값이 주어진다.

 

출력 조건

여행을 떠날 수 있는 그룹의 최대값

 

풀이

N명의 모험가의 공포도를 정렬하고, 그룹 지어진 인원을 빼며 계산한다.

import java.util.*;

class Main {

  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Integer[] arr = new Integer[n];
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }
    sc.close();

    Arrays.sort(arr, (a1, a2) -> a2-a1);

    int size = arr.length;
    int tmp = 0;
    int result = 0;
    while (true) {
      size -= arr[tmp];
      if (size >= 0) {
        tmp++;
        result++;
      } else {
        break;
      }
    }

    System.out.println(result);

  } // end main
}

전체 인원에서 공포도가 높은 모험가의 인원만큼 빼서 하나의 그룹을 만든다. 이를 반복한다.

하지만 최대 값을 구해야 하는데, 4 1 1 1 이 나온 경우, 위와 같은 코드로는 그룹 1개만 가능하다.

그래서 최대값을 구할 수 있도록 오름차순으로 변경했다. 

 

import java.util.*;

class Main {

  public static void main(String[] args) {
    
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    Integer[] arr = new Integer[n];
    for (int i = 0; i < n; i++) {
      arr[i] = sc.nextInt();
    }
    sc.close();

    Arrays.sort(arr);
    int cnt = 0;
    int result = 0;
    for(int i = 0; i < n; i++) {
      cnt++;
      if (cnt >= arr[i]) {
        result++;
        cnt = 0;
      }
    }

    System.out.println(result);

  } // end main
}

낮은 공포도부터 팀 결성하면 최대한 많은 팀은 결성할 수 있음. 먼저 혼자서도 갈 수 있는 모험가는 하나의 그룹으로 만들고 최소한의 인원으로 그룹을 짓도록 코드를 작성했다.