백준 16200 - 해커톤 (자바 - 그리디)

https://www.acmicpc.net/problem/16200

16200번: 해커톤

 

* 문제 요약

해커톤에 N 명의 학생이 참가의사를 밝혔다. 편의상 학생에 번호를 매겼고, 번호는 1부터 N까지이다.

해커톤에 참가하는 N명을 몇 개의 팀으로 나눠야 하는데, 대회 주최측에서는 팀의 갯수를 최소로 하고 싶어한다.

단, i 번 학생은 자신이 속한 팀원 수가 자기 자신을 포함해서 Xi 명 이하일 때만 참가한다고 한다.

주최측은 참가 의사를 밝힌 N 명이 모두 참여할 수 있도록 팀을 배정할 생각이며, 이 때 팀의 수를 최소로 하려고한다.

 

다음 조건을 모두 만족하게 팀을 만들어야 한다.

- 한 학생은 하나의 팀에 소속되어야 한다.

- 각 팀은 최소 한 명의 학생을 포함한다.

- 모든 i 에 대해서, i 번 학생이 속한 팀의 팀원 수는 Xi 명 이하이어야 한다.

위의 조건을 만족하면서 N 명을 팀으로 나눴을 때, 팀의 수의 최솟값을 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에는 학생의 수 N (1 <= N <= 100,000) 이 주어진다.

둘째 줄에는 N 개의 정수가 주어지고, 순서대로 X1, X2, .... XN 을 의미한다. 모든 i 에 대해서 1 <= Xi <= N 을 만족한다.

 

* 출력

첫째 줄에 팀의 수의 최솟값을 출력한다.

 

* 예시

 

* 해결 과정

입력 받은 데이터들을 오름차순으로 정렬해준 다음, 구성된 팀을 표현할 자료구조로 큐를 만들어주었다.

여기서 데이터들을 오름차순으로 정렬해준 이유는 원하는 팀원의 숫자가 가장 적은 사람을 먼저 큐에 넣은 다음, 그 숫자를 기준으로 팀을 채워주기 위해서이다.

큐에 처음으로 들어가는 팀원이 원하는 숫자를 기준으로 팀원을 채우기 위해 이중 반복문을 활용했으며, 이중 반복문 내부에서는 큐의 크기가 팀에 가장 먼저 들어간 팀원이 바라는 숫자보다 작거나 같을 동안 다음번 인덱스에 있는 팀원들을 큐에 넣어준다.

 

이와 같은 로직이 가능한 이유는 데이터들을 오름차순 정렬해줬기 때문이다.

오름차순 정렬을 해둔 상태이기 때문에 반복을 통해 다음 인덱스의 정보를 확인해도, 해당 인덱스의 팀원이 바라는 팀의 구성원 숫자는 큐에 처음으로 들어갔던 사람이 원하던 숫자보다 많거나 같을 것이기 때문에 그냥 처음에 큐에 들어간 팀원이 바라는 팀의 구성원 숫자만큼 큐의 크기가 커질때까지 이중 반복문을 돌며 계속 큐에 팀원들을 넣어주면 된다.

그러다가 처음 큐에 들어간 사람이 바라는 팀원의 숫자와 큐의 크기가 같아지면 더이상 팀원들을 넣지 않고 팀의 갯수를 1 증가시킨 다음 큐를 완전히 비워준다.

 

이중 반복문이 끝난 이휴에 큐의 크기가 0 이 아니라면 아직 만들어져야 할 팀이 하나 더 있다는 뜻이므로 팀의 갯수를 마지막으로 다시 한번 1 증가시킨다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int result = 0;

        int count = Integer.parseInt(br.readLine());
        String[] input = br.readLine().split(" ");
        int[] team = new int[count];

        for (int i = 0; i < team.length; i++) {
            team[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(team);

        Queue<Integer> teamQueue = new LinkedList<>();
        for (int i = 0; i < team.length; i++) {
            int size = team[i];
            for (; i < team.length; i++) {
                if (teamQueue.size() < size) {
                    teamQueue.offer(team[i]);
                } else {
                    result++;
                    i--;
                    teamQueue.clear();
                    break;
                }
            }
        }
        if (!teamQueue.isEmpty()) {
            result++;
        }

        bw.write(result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

원하는 팀원의 숫자가 작은 사람들끼리 묶어서 팀을 만들고 원하는 팀원의 숫자가 많은 사람들끼리 묶어서 팀을 만들어주었다.

각 반복마다 현재 최대 크기로 설정해둔 팀의 크기와 비교해서 현재 팀원이 팀에 들어가도 괜찮은지 여부만 확인해주며 만들어지는 팀의 갯수를 체크했다.

매 반복마다 조건에 따라 최적의 선택을 내리게끔 로직을 작성했다. 그러므로 그리디 알고리즘 문제라고 할 수 있다.