모험가 길드

1. 문제 

모험가 길드가 있습니다. N명의 모험가를 대상으로, 공포도를 측정 했을 때, 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 합니다. 이 때, 모험가 그룹의 최대 갯수를 출력 하시오. 첫째 줄에 N의 값과 둘째 줄의 N명의 대한 공포도가 입력으로 주어 집니다. (1 <= N <= 100,000)

 

 

2. 입력

5

2 3 1 2 2

 

 

3. 출력

2

 

 

3. 접근

1. 이 문제는 그리디로 접근 할 수 있습니다.

2. 전체 공포도를 오름 차순으로 정렬 후

3. 그룹 인원 cnt를 1씩 증가 시켜 줍니다.

4. 그리고 매번, group[i] 현재 인원의 공포도가 cnt 보다 작거나 같으면, 그룹을 결성 합니다.

5. 그룹의 수를 1증가 시키고, cnt를 초기화 해줍니다.

 

import java.util.Arrays;

public class Page311 {
    // 모험가 길드
    // page 311
    public static void main(String[] args) {
        int N = 5;
        int[] group = new int[]{2, 3, 1, 2, 2};
        System.out.print(new Page311().solution(N, group));
    }

    // N <= 100,000
    private int solution(int n, int[] group) {
        Arrays.sort(group);

        int groupCnt = 0, cnt = 0;

        for (int i = 0; i < n; i++) {
            cnt++;
            if (group[i] <= cnt) {
                groupCnt++;
                cnt = 0;
            }
        }

        return groupCnt;
    }
}