그리디 - 모험가 길드

문제

---

- 한 마을에 모함가각 n명 있습니다. 모험가 길드에서는 n명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어집니다.

- 모험가 길드장인 동빈이는 그룹을 안전하게 구성하고자 공포도가 x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했습니다.

- 동빈이는 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금합니다. n명의 모험가에대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하세요.

 

 

입력조건

- 첫째 줄에 모험가의 수 n이 주어집니다 (1<= n <=100,000)

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

ex)
5

2 3 1 2 2

 

출력조건

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

ex)2

 

 

 

문제해결

---

1) 정답

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	int n = sc.nextInt();
	
	int[] arr = new int[n];
	for(int i=0;i<n;i++) {
		arr[i] = sc.nextInt();
	}
	Arrays.sort(arr); //우선 오름차순 정렬
	
	int result = 0; //여행 떠날수있는 그룹 수
	int count = 0; //현재 그룹에 포함된 모험가의 수
	for(int i=0;i<n;i++) { //공포도를 낮은 것부터 하나씩 확인하며
		count++; //현재 그룹에 해당 모험가를 포함시키기
		if(count>=arr[i]) { //현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 생성
			result++; //총 그룹의 수 증가
			count = 0; //현재 그룹에 포함된 모험가의 수 초기화
		}
	}
	System.out.println(result);
}

 

 

 

해설

---

1. 오름차순 정렬 이후 공포도가 낮은 모험가부터 하나씩 확인한다

2. 앞에서부터 공포도를 하나씩 확인하며 현재 그룹에 포함된 모함가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 이를 그룹으로 정해서 바로 여행을 보내면 됨

3. 이러한 방법을 이용하면 공포도가 오름차순으로 정렬되어 있다는 점에서, 항상 최소한의 모험가의 수만 포함하여 그룹을 결성하게 됨

 

 

 

- 오름차순 정렬 이후 공포도가 낮은것부터 하나씩 확인하는 것까지는 생각했는데 현재 그룹을 count 변수에 담아서 지금 체크하고 있는 사람의 공포도와 현재 그룹 사람 수를 확인하는 작업(if(count>=arr[i] 부분)을 생각하지 못해서 제한시간 내에 풀지 못했다