[이코테][기출] 01. 모험가 길드

<문제 분석>

모험가가 N명 있다. 공포도가 X인 모험가는 반드시 X명 이상의 모험가 그룹이 필요하다.

최대 몇명의 모험가 그룹을 만들 수 있는가?

 

<첫번째 풀이 - 실패>

배열 A[N]을 정의해서 공포도를 저장한다.

오름차순으로 정렬한다.

for (i = N to 0)

A[N]의 공포도만큼 i를 전진하고, count++한다.

(10분 걸림)

 

<후기>

1. 오름차순으로 정렬하는 것까지는 생각함.
2. 하지만 공포도가 낮은 것부터 확인해서 일단 그룹에 모험가를 포함시키고 그 수와 현재 확인중인 공포도를 비교하는 로직은 생각하지 못함.

 

---------------------------------------------------------------------------------------------

 

<해설>

공포도를 기준으로 오름차순으로 정렬을 한다.

공포도가 낮은 모험가부터 확인해서, 현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 그룹을 결성할 수 있다.

 

<정답코드>

import java.util.Scanner;
import java.util.Arrays;

// [이코테](그리디) 01. 모험가 길드

public class Main {
    static int N;
    static int A[];
    
    public void InputData() {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }
    }

    static int group = 0; // 모험가 그룹의 수
    static int count = 0; // 현재 그룹에 포함된 모험가의 수
	public void Solve() {
        // 먼저 공포도를 오름차순으로 정렬한다.
        Arrays.sort(A);

        // 공포도를 낮은 순부터 하나씩 확인한다.
        for (int i=0; i<N; i++) {
            count++; // 일단 그룹에 모험가를 포함시킨다.
            if (count >= A[i]) { // 포함된 모험가의 수가 현재 공포도와 같거나 크면
                group++; // 그룹의 수를 +1 중가
                count = 0; // 현재 그룹에 포함된 모험가 수 초기화
            }
        }
        System.out.println(group);
	}
    
	public static void main (String[] args)
	{
		Main m = new Main();
		m.InputData();
        m.Solve();
	}
}