121. 모험가 길드

• 한 마을에 모험가가 N명 있습니다.

• 모험가 길드에서는 N명의 모험가를 대상으로 '공포드'를 측정

  • 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.

• 동빈이는 최대 몇개의 모험가 그룹을 만들 수 있는지 궁금합니다.

  • N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요

예를 들어, N = 5이고, 각 모험가의 공포도가 다음과 같다고 가정.
2 3 1 2 2

• 그룹 1에 공포도가 1,2,3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가2인 남은 두 명을 넣게 되면, 총 2개의 그룹을 만들 수 있습니다.

• 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없습니다.

• 입력조건

  • 첫째 줄에 모험가의 수 N이 주어집니다. (1 ≤ N ≤ 100,000)

  • 둘째 줄에 각 모험가의 공포도의 값을 N이하의 자연수로 주어지며, 각 자연수는 공백으로 구분합니다.

• 출력조건

  • 여행을 떠날 수 있는 그룹 수의 최댓값을 출력합니다.

1. 그리디 알고리즘

n = int(input())
data = list(map(int, input().split()))

data.sort()
result = 0
count = 0 #현재 그룹에 포함된 모험가의 수

for i in data: #ex) [1 2 2 2 3] -> [1][2,2] 2 3(2만큼 차도 i는 3을 가리킴)
  count += 1
  if count >= i: #현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
    result += 1
    count = 0

print(result)


   

2. C++ 코드

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;

int main(void) {
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    sort(arr.begin(), arr.end());

    int result = 0; // 총 그룹의 수
    int count = 0; // 현재 그룹에 포함된 모험가의 수

    for (int i = 0; i < n; i++) { // 공포도를 낮은 것부터 하나씩 확인하며
        count += 1; // 현재 그룹에 해당 모험가를 포함시키기
        if (count >= arr[i]) { // 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
            result += 1; // 총 그룹의 수 증가시키기
            count = 0; // 현재 그룹에 포함된 모험가의 수 초기화
        }
    }

    cout << result << '\n'; // 총 그룹의 수 출력
}

3. Java 코드

import java.util.*;

public class Main {

    public static int n;
    public static ArrayList<Integer> arrayList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            arrayList.add(sc.nextInt());
        }

        Collections.sort(arrayList);

        int result = 0; // 총 그룹의 수
        int count = 0; // 현재 그룹에 포함된 모험가의 수

        for (int i = 0; i < n; i++) { // 공포도를 낮은 것부터 하나씩 확인하며
            count += 1; // 현재 그룹에 해당 모험가를 포함시키기
            if (count >= arrayList.get(i)) { // 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
                result += 1; // 총 그룹의 수 증가시키기
                count = 0; // 현재 그룹에 포함된 모험가의 수 초기화
            }
        }

        System.out.println(result);
    }
}