문제 번호 10989번 : 수 정렬하기 3 - JAVA [자바]

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

10989번: 수 정렬하기 3

문제 설명

 

자바 제안시간 3초 메모리 제안 512MB를 충족하는 정렬을 해야 하는 문제이다. 제안시간이 지금까지 문제와는 TEST 데이터에 비해 확연히 부족하다. 그래서 가장 빠른 카운팅 정렬을 사용해 문제를 풀어야 한다.

 

문제 풀이

해당 문제에서 가장 중요한 것은 속도입니다.

속도가 걸려서 문제를 풀지 못하는 경우가 많습니다.

제가 아는 빠른 정렬은 합병 정렬과 힙 정렬, 카운팅 정렬입니다.

카운팅 정렬로 문제를 해결해 보도록 하겠습니다. 카운팅 정렬에 관해서는 이 글을 보고 오는 것을 추천드립니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[10001];

        for (int i = 0; i < n; i++) {
            arr[Integer.parseInt(br.readLine())]++;
        }

        br.close();
        /*
        해당 배열을 그냥 처음부터 있는 수만큼 출력한다는 개념으로
        for문과 while문을 만들어 구현한다.
         */
        for (int i = 0; i < arr.length; i++) {

            while (arr[i]-- > 0) {
                sb.append(i).append('\n');
            }
        }
        System.out.println(sb);
    }
}

중요한 것은 BufferReader와 StringBuilder을 사용해서 풀어야 한다는 것입니다.

입력과 출력도 시간 사용에 포함되는데 그냥 scanner와 system.out.println을 사용하면 시간을 충족하지 못해 문제를 풀 수 없게 됩니다.