[정렬#2] 백준 2750번: 수 정렬하기 2 JAVA

2751번: 수 정렬하기 2 (acmicpc.net

2751번: 수 정렬하기 2

문제

---

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

 

 

 

입력

---

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

 

 

 

출력

---

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

 

 

예제 입출력

---

예제 입력	예제 출력
5 5 4 3 2 1	1 2 3 4 5

 

 

풀이

---

 이번 문제는 수 정렬하기 1번 문제와 비슷하지만 조건이 수의 범위가 더 커졌고 시간 제한이 더 빡세졌다. 이번 문제도 수 정렬하기 1번에서 사용했던 퀵정렬 알고리즘으로 문제를 제출했지만 시간초과 판정을 받았다. 각 정렬 알고리즘 별 시간 복잡도 이해가 중요하다고 볼 수 있다. 이번 문제는 퀵 정렬 알고리즘을 저격?한 문제라고 볼 수있다.

 

 그 이유는 퀵 정렬은 시간 복잡도가 O(nlogn)으로 매우 빠른 알고리즘인 것은 맞다. 하지만 최악의 경우 O(n**2)이므로 이 조건을 노린 문제이다. 따라서 퀵정렬을 직접 구현한 알고리즘이나 퀵 정렬로 이루어져 있는 Arrays.sort()를 쓰지 못하게 저격한 데이터가 있어서 이러한 방법을 썼다면 시간 초과 판정을 받게된다.

 

 따라서 최악의 경우에도 O(nlogn)을 보장하거나, O(n)에 가까운 정렬 알고리즘을 사용해야 한다. 두가지 방법이 있다.

첫번째는 Collections.sort()를 사용하는 방법과 두번째로 CountingSort()를 사용하는 방법이다. 

 

 

코드

---

1. Collection.sort()

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		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 result:list) {
			bw.write(result + "\n");
		}
		bw.flush();
		bw.close();
		
	}
	
}

 

 

 

2. Counting Sort()

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

public class Main {
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		
		// 수의 범위 -1000000 ~ 1000000
		// 기준점 0 = index 1000000으로 시작
		boolean[] count = new boolean[2000001];
		
		
		for(int i=0; i<n; i++)
			count[Integer.parseInt(br.readLine()) + 1000000] = true;
		
		
		for(int i=0; i<count.length; i++) {
			if(count[i] == true)
				bw.write((i-1000000) + "\n");
		}
		bw.flush();
		bw.close();
	}
	
}