[이것이 코딩 테스트다 with Python] 모험가 길드(Java)

Goal

“이것이 코딩 테스트다 with Python” 교재의 문제를 분석하고 코드와 함께 이해해보기 위한 글입니다.

문제 분석

먼저 시간 복잡도를 고려해보면 N값이 100,000까지 커질 수 있으므로 O(nlogn) 시간 복잡 알고리즘까지 사용할 수 있습니다.

그룹에 있는 모험가들의 최대 공포도만큼 그 그룹의 모험가 수가 보장되어야 하기 때문에, 주어진 모험가들의 공포도를 정렬해서 순서대로 그룹화하면 가능한 그룹 수의 최대를 보장할 수 있습니다.

코드 구현

public class AdventureGuild { //p311
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int adventurerNum = Integer.parseInt(br.readLine()); //모험가 수
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Integer> arrayList = new ArrayList<>(); //주어지는 모험가 무리의 공포도

        for (int i = 0; i < adventurerNum; i++) {
            arrayList.add(Integer.parseInt(st.nextToken()));
        }

        Collections.sort(arrayList); //공포도 오름차순 정렬을 해서

        int answer = 0; //그룹 수
        int cnt = 0; //모험가 수

        for (int i = 0; i < adventurerNum; i++) { //순서대로 공포도를 체크하는데
            cnt += 1; //모험가를 그룹에 추가하다가
            if (cnt >= arrayList.get(i)) { //그룹의 모험가 수가 새로운 모험가의 공포도보다 크면 
                answer += 1; //그룹 완성
                cnt = 0; //초기화
            }
        }
        bw.write(answer);
        br.close;
        bw.close;
    }
}