2751번 - JAVA

수 정렬하기 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2초	256MB	171025	47382	32465	30.167%

 

문제

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

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

 

 

출력

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

 

 

 

 

---

예제 입력 1

5
5
4
3
2
1

 

예제 출력 1

1
2
3
4
5

 

 

 

 

---

 

 

정답 코드

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

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());
		
		ArrayList<Integer> list = new ArrayList<>();
		
		for(int i = 0; i < N; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(list);
		
		for(int value : list) {
			sb.append(value).append('\n');
		}
		System.out.println(sb);
	}
}

 

 

 

• StringBuilder sb = new StringBuilder();
  • ArrayList의 값을 그대로 출력한다면 부하가 크고 속도도 느리기 때문에 시간 초과가 난다. 따라서 StringBuilder를 통해 속도를 빠르게 하고, 부하를 적게 가지게 할 수 있다.
• Collections.sort(arr);
  • 일반적인 배열이 아닌 리스트와 같은 배열을 정렬할 때 사용한다. 
  • Arrays.sort(arr) 보다 속도가 빠르다.
  • 기본적으로 오름차순으로 정렬된다.

 

 

 

 

해당 문제의 포인트는 배열을 정렬하는 일반적인 메서드 Arrays.sort를 사용하면 풀 수 없다는 점이다. Arrays.sort가 느린 편은 아니지만 최악의 경우 O(n2) 만큼의 시간 복잡도를 가지기 때문에 해당 문제에서 사용할 수 없다. (Arrays.sort를 사용할 수 없도록 테스트 케이스에 최악의 경우를 넣어 놨다.)

 

따라서 정렬 속도가 더 빠른 정렬을 직접 구현하여 사용하거나, 위에서 사용한 정렬 메서드인 Collections.sort를 활용하여 풀어야 한다.

 

그뿐만 아니라 StringBuilder를 통해 더욱 시간을 절약하여 풀어야 통과할 수 있다.

 

 

 

 

 

2751번: 수 정렬하기 2