알고리즘-그리디-모험가길드

알고리즘-그리디-모험가길드

 

문제 :  모험가가 N명이있으며 각 모험가마다 공포도 X가 주어진다.

            공포도가 X인 모험가는 무조건 X명 이상 모험가가 모여야한다.

            최대 몇개의 모험가 그룹을 만들수 있을까

            남는 모험가가 있어도된다.

             

             N의 범위는 1 ~ 100,000

 

 

해결방안

           1.  N의 범위가 10만    복잡도 O(Nlog(N))

            2. 최대 모험가 그룹이니 그리디 알고리즘 의심

            3. 공포도가 높은 사람을 기준으로 하면 예시가 4111으로 나오면 최대 그룹수가 1로 나와서 안됨

            4. 공포도가 낮은 사람으로 출발해서 예시가 1 2 2 2 3 으로 나오면 2와3을 버리는 식으로 진행해                     야할듯

            5. 오름차순으로 하여 사람을 한명씩 넣어서 사람수와 공포도가 크거나 일치하면 그룹을 만든다.

 

 

코드

public static void main(String[] args) throws IOException {

    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(bf.readLine());  //모험가 숫자
    StringTokenizer st= new StringTokenizer(bf.readLine()); //공포도 입력
    for ( int i=0; i<N;i++){
        Fear[i] = Integer.parseInt(st.nextToken()); // 배열에 집어넣기
    }
   // System.out.println(Arrays.toString(Fear));
    Arrays.sort(Fear);//정렬
    int Loc = 0;
    int Group=0;

    for(int j=0; j<N;j++){
        Loc +=1; //그룹에 사람넣기
        if ( Loc >= Fear[j]) {  //그룹 인원이 공포도와 같거나 크면 통과(그룹이 만들어짐)
            Group +=1;//한 그룹이 만들어짐
            Loc =0; //새로운 그룹 세팅
        }
    }
    System.out.println(Group);