이것이 코딩테스트다 모험가 길드(java)

문제

공포도가 x인 모험가는 반드시 x명 이상으로 구성된 그룹으로 참여가능하다.

 

입력 조건

첫째 줄 모험가의 수 n, 둘째 줄에 각 모험가의 공포도가 주어진다.

 

출력조건

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

 

나의 풀이

 

public class greedy01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int answer = 0;
        int[] testcase = new int[n];

        for (int i = 0; i < n; i++) {
            testcase[i] = scanner.nextInt();
        }

        //오름차순 정렬
        Arrays.sort(testcase);

        int count = 0;

        for (int i = 0; i < n; i++) {
            count++;

            if(testcase[i] <= count) {
                answer++;
                count = 0;
            }
        }

        System.out.println("answer = " + answer);

    }
}

최대 그룹을 만들기 위해서는 공포도가 낮은 사람순으로 그룹을 만드는 방식으로 진행하면 된다.

따라서 공포도를 오름차순으로 정렬을 한 다음 그룹의 수를 구하는 방식으로 진행하면 된다.

 

public class greedy01 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int answer = 0;
        ArrayList<Integer> testcase = new ArrayList<>();

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

        //오름차순 정렬
        Collections.sort(testcase);

        int count = 0;

        for (int i = 0; i < n; i++) {
            count++;

            if(testcase.get(i) <= count) {
                answer++;
                count = 0;
            }
        }

        System.out.println("answer = " + answer);

    }
}