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

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

이 문제는 정렬만 하면 간단한 문제인 것 같아서 버블정렬을 사용하여 구현해 보았다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	
		int n = sc.nextInt();
		int arr[] = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		for(int i=0; i<n; i++) {
			for(int j=i+1; j<n; j++) {
				if(arr[i] > arr[j]) {
					int temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		
		for(int i=0; i<n; i++) {
			System.out.println(arr[i]);
		}
		
	}

}

 

하지만 이 코드를 백준에 제출하여 보니 시간 초과로 오류가 발생하였고

입력받는 방식이 Scanner이라 문제가 발생한 것으로 생각하여 입력받는 방식을 BufferedReader로 바꿔보았다.

 

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

public class Main {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n];
			
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(br.readLine());
			}
	
			for(int i=0; i<n; i++) {
				for(int j=i+1; j<n; j++) {
					if(arr[i] > arr[j]) {
						int temp = arr[i];
						arr[i] = arr[j];
						arr[j] = temp;
					}
				}
			}
			StringBuilder sb = new StringBuilder();
			for(int i=0; i<n; i++) {
				sb.append(arr[i]).append('\n');
			}
			System.out.print(sb);
			
		} catch (IOException e) {
			e.printStackTrace();
		}		
	}
}

 

하지만 입력 받는 방식을 BufferedReader로 바꿨음에도 여전히 시간초과가 발생하였다.

그래서 해결 방식을 찾아보던 중 Java의 표준 라이브러리인 java.util 패키지에 포함된 정렬 메서드인 arrays.sort를 사용하면 쉽게 해결될 것 같아 적용해 보았다.

 

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

public class baekjoon10989 {

	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			int n = Integer.parseInt(br.readLine());
			int[] arr = new int[n];
			
			for(int i=0; i<n; i++) {
				arr[i] = Integer.parseInt(br.readLine());
			}
	
			Arrays.sort(arr);
			
			StringBuilder sb = new StringBuilder();
			for(int i=0; i<n; i++) {
				sb.append(arr[i]).append('\n');
			}
			System.out.print(sb);
			
		} catch (IOException e) {
			e.printStackTrace();
		}		
	}
}

 

Arrays.sort를 사용해 정렬을 하니 바로 시간 초과 문제가 해결되었다.

 

버블정렬을 사용하여 코드를 작성하였을 때는 시간복잡도가 평균 및 최악의 경우 O(n^2)으로 오래 걸린다.

하지만, Arrays.sort의 시간복잡도는 평균 경우에 (O n log n)이고 최악의 경우에만 O(n^2) 시간이 걸리기 때문에 위와 같은 문제를 해결할 수 있었던 것 같다.