반응형
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;
}
}
반응형
'Algorithm' 카테고리의 다른 글
에라토스테네스의 체(Sieve of Eratosthenes) (0) | 2020.09.23 |
---|---|
소수의 판별 (0) | 2020.09.23 |
곱하기 혹은 더하기 - 페이스북 기출 유형 (0) | 2020.09.22 |
공유기 설치 - 백준 2110번 (0) | 2020.09.22 |
파일 통계 프로그램 (0) | 2020.09.21 |