[백준 알고리즘][자바] 10989번 : 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

기본적인 수 정렬하기 시리즈 마지막 문제입니다.

이번 문제에서는 아래의 3가지 방법을 사용하여 풀어보도록 하겠습니다.

1. 직접 구현한 Counting Sort를 사용
2. Arrays.sort()를 사용
3. Collections.sort()를 사용

 

2022.05.07 - [Algorithm/Theory] - [Java] Counting Sort(카운팅 정렬)

[Java] Counting Sort(카운팅 정렬)

 

 

풀이

1-1. 직접 구현한 Countint Sort를 사용(누적합 사용)

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int max = 0;
		int[] array = new int[N];
		int[] result = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			array[i] = Integer.parseInt(br.readLine());
			max = Math.max(array[i], max); // 카운팅 배열의 크기 구하기
		}
		
		int[] counting_array = new int[max + 1];
		
		for(int i = 0 ; i < array.length ; i++) {
			counting_array[array[i]]++; //  카운팅 배열 카운트
		}
		
		for(int i = 1 ; i < counting_array.length ; i++) {
			counting_array[i] += counting_array[i-1]; // 누적합
		}
		
		for(int i = array.length - 1 ; i >= 0 ; i--) {
			result[--counting_array[array[i]]] = array[i]; // result 배열 만들기
		}
		
		for(int i = 0 ; i < N ; i++) {
			bw.write(String.valueOf(result[i]) + "\n");
		}
		
		br.close();
		bw.flush();
		bw.close();
	}
}

 

 

 

1 - 2. 직접 구현한 Countint Sort를 사용(누적합 사용 X)

 

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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[] counting_array = new int[10001];
		int[] array = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			array[i] = Integer.parseInt(br.readLine());
		}
		
		for(int i = 0 ; i < array.length ; i++) {
			counting_array[array[i]]++; //  카운팅 배열 카운트
		}
		
		for(int i = 0 ; i < 10001 ; i++) {
			while(counting_array[i] > 0) {
				bw.write(String.valueOf(i) + "\n");			
				counting_array[i]--;
			}
		}
		
		br.close();
		bw.flush();
		bw.close();
	}
}

 

누적합 과정을 거치지 않으면 확실히 시간과 메모리의 차이가 있음을 알 수 있습니다.

누적합 과정을 거치는 이유는 result로 새로운 배열을 만들 때 인덱스를 지정해주기 위해서 과정이 필요합니다.

 

 

2. Arrays.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 NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(br.readLine());
		int[] array = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			array[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(array);
		
		for(int i = 0 ; i < N ; i++) {
			bw.write(String.valueOf(array[i]) + "\n");
		}
		
		br.close();
		bw.flush();
		bw.close();
	}
}

 

 

 

3. Collections.sort() 사용

 

package number_10989;

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 Main2 {

	public static void main(String[] args) throws NumberFormatException, 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<Integer>();
		
		for(int i = 0 ; i < N ; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(list);
		
		for(int i = 0 ; i < N ; i++) {
			bw.write(String.valueOf(list.get(i)) + "\n");
		}
		
		br.close();
		bw.flush();
		bw.close();
	}
}

 

 

 

정리

아래에서부터 차례대로

1. Counting Sort 사용(누적합 사용)

2. Counring Sort 사용(누적합 사용 X)

3. Arrays.sort() 사용

4. Collections.sort() 사용

 

1번과 2번은 누적합 과정의 유무에 따라 최적화의 차이가 메모리와 시간에서 드러나고 있습니다.

Arrays.sort()는 최악의 경우 시간 복잡도가 O(n^2)까지 나올 수 있는데, 성공이 되는 것으로 봐서는 저격 데이터는 없는 거 같습니다. 하지만 시간제한이 3초라는 걸 생각하면 빠듯하네요.

Collections.sort()는 List객체를 사용하기 때문에 메모리 초과가 발생하는 것을 알 수 있습니다.