모험가 길드 문제

그리디
현재 상황에서 지금 당장 좋은 것만 고르는 방법

✅ 문제

한 마을에 모험가가 N명 있습니다. 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.
N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

입력 예시
5
2 3 1 2 2

출력 예시
2

💻 코드

import java.util.*;

public class Greedy_Adeventure {

     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);
        }

}

📝 정리

그리디 활용 - Sorting 이후에 배열을 크기 순으로 차례로 불러오면서 그 count를 늘리는 방식의 풀이 방법을 생각 못했음..
-> count 값과 get(i) 값이 같을 경우 그 때 그룹을 짓는 방법을 활용하는 아이디어