[Java] BOJ 10989 수 정렬하기 3

문제 

문제 링크 https://www.acmicpc.net/problem/10989

• N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.
• 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

아이디어

• 배열을 1부터 10000까지 만들어서 입력받는 수에 해당하는 배열의 값을 + 1해줘서 몇번 나왔는지 기록한다.
  • 2가 입력되면 [0, 0, 1, 0, 0 ...] 이런식으로 기록한다.
• 그리고 1부터 10000까지 반복문을 돌면서 해당 배열 값이 0이 아니면 그 배열 값만큼 해당 배열 번째 수를 출력한다.

겪은 시행착오

• 시간초과가 정말 많이 났다.. 처음에 배열로 할 생각을 안하고 Arrays.sort()로 했었는데 시간초과가 나고.. 다음에 또 시간초과가 났는데 배열을 사용한 위에 방법을 사용했는데도 시간초과가 났다. 
• 그 다음에는 1부터 10000까지 돌리는 반복문이 문제인가 생각해서 TreeSet에다가 입력되는 숫자들을 저장해서 반복문을 돌리지 않고 저장된 숫자로 바로 접근해서 저장된 숫자번째의 배열 값만큼 순번을 출력하는 방식으로 했지만 시간초과가 났다. 
• 알고보니 TreeSet 자체가 안에서 자체 정렬을 하기 때문에 시간초과가 나는 것이였다.. (그것때문에 Set 중에 TreeSet을 골랐는데.. 이것때문에 시간초과가 날줄은 몰랐다....ㅜㅜ)
• 결국 정답은 위에 방법을 사용하면서 일일이 System.out.prinln을 쓰지 않고 StringBuilder를 사용하니 성공했다... ㅜ

정답을 위해 발판이 된 시간초과들....

험난한 여정이였다...

코드

import java.io.*;
import java.util.*;

public class BOJ10989 {
    public static void main(String[] args) throws Exception{
        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++) {
            int n = Integer.parseInt(br.readLine());

            // 수가 입력되면 그 수번째 배열을 카운트 + 1
            arr[n] = arr[n] + 1;
        }

        // 몇개 출력되었는지 카운트할 변수
        int cnt = 0;

        // 수의 범위가 1부터 10000까지므로
        for(int i = 1; i < 10001; i++){
            // arr의 i번째가 0이 아니라면 입력이 된 수이기 때문에
            if(arr[i] != 0){
                // 입력된 횟수만큼
                for(int j = 0; j < arr[i]; j++){
                    // 해당 숫자를 저장
                    sb.append(i + "\n");
                    // 출력 카운트 + 1
                    cnt = cnt + 1;
                }
            }

            // 만약 출력 카운트가 몇개 입력되었는지 알려주는 N과 같다면 반복문 종료
            if(cnt == N){
                break;
            }
        }

        System.out.println(sb);
    }
}