[백준] 10989번 - 수 정렬하기 3

 

이 문제를 풀기에 앞서 같은 문제지만 조금 더 간단한 문제들은 아래 링크를 따라가면 있다.

https://ddamdoo.tistory.com/100

https://ddamdoo.tistory.com/101

 

 

import java.util.Arrays;
import java.util.Scanner;

public class p10989 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[] ary = new int[n];

		for (int i = 0; i < n; i++) {
			ary[i] = sc.nextInt();
		}

		Arrays.sort(ary);

		for (int i = 0; i < n; i++) {
			System.out.println(ary[i]);
		}
	}
}

 

Arrays.sort 를 사용하면 간단하지만 이는 시간복잡도 O(n^2)이므로 시간초과가 났다.

그래서 최대한 메모리 시간을 줄이기 위해서 Scanner대신 bufferedReader, system.out.println 대신 bufferedWriter를 이용하였고, sort함수 대신 크기가 10001인 배열을 만들어 인덱스에 값을 늘리고 이 값을 출력하는 방법으로 문제를 해결하였다.

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

public class p10989 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int[] ary = new int[10001];
		int n = Integer.parseInt(br.readLine());

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

		for (int i = 1; i <= 10000; i++) {
			if (ary[i] > 0) {
				for (int j = 0; j < ary[i]; j++) {
					bw.write(i + "\n");
				}
			}
		}
		bw.close();
	}
}