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

www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

---

• 문제

 

 

 

정렬의 가장 기초적인 문제다!

 

---

• 9가지 방법을 이용하여 풀이한다.

먼저 정렬 방법은 여러가지가 있지만 가장 쉽게 쓸 수 있는 방법은 크게 3가지가 있다.

 

먼저, 선택정렬이다.

 

첫 번째 인덱스부터 시작하여 뒤의 인덱스들의 값들과 비교하여 최솟값들을 차곡차곡 쌓아나가는 방법이다. 가장 구현하기 쉽다는 장점이 있으나 시간복잡도가 O(n²) 으로 그리 좋은 성능의 알고리즘은 아니다. 아마 정렬을 구현해보거나 접해본 분들이라면 한 번 쯤은 보았을 코드다.

 

[선택정렬]

int[] arr; // 이미 초기화 되어 있는 배열이라고 가정

for(int i = 0; i < arr.length - 1; i++) {
	for(int j = i + 1; j < arr.length; j++) {
    
		if(arr[i] > arr[j]) {
			// 값 교환
			int temp = arr[j];
			arr[j] = arr[i];
			arr[i] = temp;
		}
	}
}

 

 

 

두 번째 방법은 가장 간단한 방법으로, Arrays.sort() 메소드를 쓰는 방법이다. Arrays.sort() 는 자바에서 기본으로 제공되는 메소드로, 자체 정렬 알고리즘을 구현 할 필요 없이 sort() 안에 배열만 넣어주면 자동으로 해당 배열이 정렬되어 나온다. Arrays.sort() 의 경우 dual-pivot Quicksort 알고리즘을 쓰고 있기 때문에 시간복잡도는 평균 O(nlogn) 으로 좋은 성능을 내고 있다. 물론 최악의 경우에는 O(n²)  이기 때문에 저격 데이터를 넣을 경우 효율은 떨어질 수 있다. 이와 관련해서는 수 정렬하기 2 을 풀면 알 수 있다. 그럼에도 나쁘지 않은 알고리즘인 것은 맞다. (사실상 직접 비교 정렬 알고리즘은 O(nlogn) 이 마지노선 시간복잡도로 보고 있다.)

 

아래 Java API문서에서 Arrays.sort 에 대한 설명이다.

https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/Arrays.html#sort(int%5B%5D)

 

 

 

 

 

세 번째로는 Counting Sort 정렬 알고리즘을 사용하는 방법이다.

정확히 말하자면 Counting Sort를 '응용한' 방법이다. 좀 더 구체적으로 말하자면 값을 비교하면서 정렬하는 것이 아니라 각 입력받은 값을 index 으로 하여 해당 값의 출현 빈도수를 체크하고, 출력하는 방법을 사용하는 것이다. 이 경우에는 시간복잡도가 O(n)으로 매우 빠른 알고리즘에 속한다. 자세한 내용은 아래 내용을 참고하길 바란다.

 

st-lab.tistory.com/104

카운팅 정렬 (Counting Sort / 계수 정렬) _ Java[자바]

 

 

 

이렇게 3가지의 정렬 방법을 써보면서 각 입력 방법을 달리하여 써 볼 것이다.

 

그리고 이 3가지 알고리즘에 입출력 방법을 달리하여 풀어 볼 것인데, 다음과 같이 방법을 제시할 것이다.

1. 선택 정렬 + Scanner
2. 선택 정렬 + BufferedReader
3. 선택 정렬 + BufferedReader + StringBuilder
4. Arrays.sort + Scanner
5. Arrays.sort + BufferedReader
6. Arrays.sort + BufferedReader + StringBuilder
7. 카운팅 정렬 + Scanner
8. 카운팅 정렬 + BufferedReader
9. 카운팅 정렬 + BufferedReader + StringBuilder

 

이 번 포스팅에서 각각의 성능을 비교하고, 앞으로 있을 정렬 알고리즘에서 반복 설명하지 않고 이 글을 참고할 수 있도록 이 번 포스팅에서 최대한 많이 알아가도록 하셨으면 한다.

 

---

• 풀이

- 방법 1 : [선택 정렬(Selection Sort) + Scanner]

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}

		// Selection sort
		for(int i = 0; i < N - 1; i++) {
			for(int j = i + 1; j < N; j++) {
				if(arr[i] > arr[j]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
		
		for(int val : arr) {
			System.out.println(val);
		}

	}
}

 

 

가장 기본적인 방법이라 할 수 있다.

아마 대부분의 언어에 대해 학습 할 때 한 번쯤은 구현해볼 것이다.

 

 

---

- 방법 2 : [선택 정렬(Selection Sort) + BufferedReader]

 

 

 

입력 방법을 바꾼 방식이다. 알고리즘은 선택 정렬로 동일하다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		// Selection sort
		for(int i = 0; i < N - 1; i++) {
			for(int j = i + 1; j < N; j++) {
				if(arr[i] > arr[j]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
		
		for(int val : arr) {
			System.out.println(val);
		}

	}
}

 

 

 

 

 

---

- 방법 3 : [선택 정렬(Selection Sort) + BufferedReader + StringBuilder]

 

 

 

출력 방법또한 반복적으로 출력을 해주는 것이 아닌, 하나의 문자열로 이어 한 번에 출력해주는 방식이다. 마찬가지로 성능면에서 단일 반복 출력에 비해 좋은 성능을 갖고 있다.

 

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

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());
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		// Selection sort
		for(int i = 0; i < N - 1; i++) {
			for(int j = i + 1; j < N; j++) {
				if(arr[i] > arr[j]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
		
		for(int val : arr) {
			sb.append(val).append('\n');
		}
		System.out.println(sb);
	}
}

 

 

 

 

 

---

- 방법 4 : [Arrays.sort + Scanner]

 

 

 

자바에서 기본적으로 제공해주는 정렬 메소드다. 사용자 구현이 따로 필요없고, Arrays 패키지만 import 해준 뒤 sort 메소드를 사용하면 된다.

 

import java.util.Scanner;
import java.util.Arrays;

public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}

		// 정렬 메소드
		Arrays.sort(arr);
		
		for(int val : arr) {
			System.out.println(val);
		}

	}
}

 

 

 

 

 

 

---

- 방법 5 : [Arrays.sort + BufferedReader]

 

 

 

방법 4에서 입력 방식을 BufferedReader 로 변경한 방식이다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		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);
		
		for(int val : arr) {
			System.out.println(val);
		}

	}
}

 

 

 

 

---

- 방법 6 : [Arrays.sort + BufferedReader + StringBuilder]

 

 

 

마찬가지로 출력또한 더 효율적으로 바꾼 코드다.

 

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

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());
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}

		// 정렬 메소드
		Arrays.sort(arr);
		
		for(int val : arr) {
			sb.append(val).append('\n');
		}
		System.out.println(sb);

	}
}

 

 

 

 

 

 

 

 

---

- 방법 7 : [카운팅 정렬 + Scanner]

 

 

 

필자가 앞서 잠깐 언급했던 정렬 방법 중 하나다. 중복되는 수는 없다고 하니 boolean 배열을 사용하여 카운팅 정렬 응용을 해보고자 한다. 자세한 방법은 아래 코드에서 확인하면 된다.

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
        
		/*
		  range : -1000 ~ 1000
		  0 은 index[1000] 을 의미
		*/
		boolean[] arr = new boolean[2001];
		
		for(int i = 0; i < N; i++) {
			arr[in.nextInt() + 1000] = true;
		}

		// 정렬 과정이 따로 필요 없음
		
		for(int i = 0; i < 2001; i++) {
			if(arr[i]) {
				System.out.println(i - 1000);
			}
		}
	}
}

 

 

 

 

 

---

- 방법 8 : [카운팅 정렬 + BufferedReader]

 

 

 

카운팅 정렬 알고리즘에 BufferedReader 로 입력받는 방식이다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
        
		/*
		  range : -1000 ~ 1000
		  0 은 index[1000] 을 의미
		*/
		boolean[] arr = new boolean[2001];
		
		for(int i = 0; i < N; i++) {
			arr[Integer.parseInt(br.readLine()) + 1000] = true;
		}

		// 정렬 과정이 따로 필요 없음
		
		for(int i = 0; i < 2001; i++) {
			if(arr[i]) {
				System.out.println(i - 1000);
			}
		}
	}
}

 

 

 

 

 

 

---

- 방법 9 : [카운팅 정렬 + BufferedReader + StringBuilder]

 

 

출력 또한 StringBuilder 로 변경해본다.

 

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

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());
        
		/*
		  range : -1000 ~ 1000
		  0 은 index[1000] 을 의미
		*/
		boolean[] arr = new boolean[2001];
		
		for(int i = 0; i < N; i++) {
			arr[Integer.parseInt(br.readLine()) + 1000] = true;
		}

		// 정렬 과정이 따로 필요 없음
		
		for(int i = 0; i < 2001; i++) {
			if(arr[i]) {
				sb.append(i - 1000).append('\n');
			}
		}
		System.out.println(sb);
	}
}

 

 

 

 

 

 

 

 

 

 

 

 

 

---

• 성능

 

 

위에서 부터 순서대로

 

채점 번호 : 20082097  -  방법 9 : 카운팅 정렬 + BufferedReader + StringBuilder

채점 번호 : 20082092  -  방법 8 : 카운팅 정렬 + BufferedReader 

채점 번호 : 20082084  -  방법 7 : 카운팅 정렬 + Scanner

채점 번호 : 20082074  -  방법 6 : Arrays.sort + BufferedReader + StringBuilder

채점 번호 : 20082070  -  방법 5 : Arrays.sort + BufferedReader

채점 번호 : 20082060  -  방법 4 : Arrays.sort + Scanner

채점 번호 : 20082053  -  방법 3 : 선택 정렬 + BufferedReader + StringBuilder

채점 번호 : 20082045  -  방법 2 : 선택 정렬 + BufferedReader

채점 번호 : 20082036  -  방법 1 : 선택 정렬 + Scanner

 

 

보이는대로 대체적으로 입출력 과정에서 차이가 난다.

 

또한 카운팅 정렬 > Arrays.sort > 선택 정렬 순으로 성능이 좋다는 것 또한 볼 수 있다. 특히나 정렬 할 데이터가 크면 클 수록 시간은 더욱 차이가 나게 되므로 반드시 방법 7, 8, 9 는 익혀두시길 바란다.

 

 

---

• 정리

 

 

정렬 문제의 가장 기초적인 접근방법들을 알아보았다. 정렬 카테고리의 첫 문제인만큼 다양한 접근 방법을 제시하려 했으니, 각 방법마다의 성능을 비교하면 좋을 것 같다. 앞으로의 정렬문제들을 푸는데 있어 가장 뼈대가 되는 기본 중의 기본이라 할 수 있을 정도로 도움이 될 것이다.