[백준/Java]Q2751

백준 알고리즘 12단계 정렬 2751번 문제입니다.

---

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

[입력]

- 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

- 둘째 줄부터 N개의 줄에는 수가 주어진다.

 

[조건]

- 절댓값이 1,000,000보다 작거나 같은 정수이다.
- 수는 중복되지 않는다.
- 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
- 제한 시간 2초

 

풀이

앞선 2750 문제와 내용은 같지만 조건이 다른 문제였다.

주어지는 수의 개수가 1000000까지 제한되며, 2초안에 정렬되어야 한다.

풀이 언어의 내장 함수를 추천하는 것으로 보아 Java의 정렬 함수를 찾아 풀어야할 것 같았다.

시간을 줄이기 위해 Scanner 대신 BuffredReader 클래스를 사용했고 Java의 정렬 함수 중 하나인 Arrays.sort()를 먼저 시도했다. 하지만 시간 초과가 났다.

Arrays.sort()에 대해 간략히 정리하면 듀얼피봇 퀵정렬 알고리즘이 사용되어 O(n log n)의 시간 복잡도를 제공한다. 하지만 최악의 경우 O(n²) 이라는 시간 복잡도를 고려해야 한다.

package com.baek.algo.step12;

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

public class Q2751 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

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

		int[] a = new int[n];

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

		Arrays.sort(a);

		for(int num : a) {
			System.out.println(num);
		}

		bf.close();
	}
}

 

다음으로 Collection 클래스의 sort() 메소드를 사용해봤다.

Collection.sort()는 반복병합 및 삽입 정렬 알고리즘을 사용하고 O(n) ~ O(n log n) 시간 복잡도를 보장한다는 점에서 Arrays.sort()보다 빠를 것으로 예상된다.

 

Collection.sort() 메소드는 리스트를 인자값으로 넘겨야했기 때문에 배열이 아닌 리스트로 값을 담고 정렬했다.

그럼에도 시간 초과가 나서 결국 구글에 힘을 빌려 해결할 수 있었다.

원인은 결과를 출력하는 곳에 있었다. 루프를 돌며 리스트의 값을 꺼내면 안되고 StringBuider를 사용해서 한번에 출력해줘야 했다.

 

소스

package com.baek.algo.step12;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Q2751 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb  = new StringBuilder();

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

		List<Integer> list = new ArrayList<Integer>();

		for(int i = 0; i < n; i++) {
			list.add(Integer.parseInt(bf.readLine()));
		}

		Collections.sort(list);

		for(int num : list) {
			sb.append(num).append("\n");
		}

		System.out.println(sb);

		bf.close();
	}
}

 

참고

[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]