[백준알고리즘] 2750번 : 수 정렬하기

백준 알고리즘 문제입니다.

자료구조는 배열과 ArrayList를 이용하였고,

알고리즘은 버블 정렬, 퀵 정렬로 문제 풀이를 하였습니다.

1. 버블 정렬

  1.1) 배열을 이용한 버블 정렬

package sort; import java.util.Scanner; // 백준알고리즘 2750번 : 수 정렬하기 // 버블정렬로 정렬하기 // 문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. // 입력 : 첫째 줄에 수의 개수 N(1<=N<=1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. // 이 수는 절대값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. // 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. // 예제 입력 예제 출력 // 5 1 // 5 2 // 2 3 // 3 4 // 4 5 // 1 public class BubbleSort_Array { // 오름차순 버블 정렬 public void sort(int arr[]){ int temp = 0; for(int i=0; i<arr.length; i++){ for(int j=0; j<arr.length-1; j++){ if(arr[j] > arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); BubbleSort_Array bSort = new BubbleSort_Array(); int test_case = scanner.nextInt(); // 수의 개수 만큼 배열 크기 지정 int arr[] = new int[test_case]; // 수의 개수 만큼 배열에 수 저장 for(int i=0; i<test_case; i++) arr[i] = scanner.nextInt(); // 버블 정렬 bSort.sort(arr); // 정렬된 수 출력 for(int i=0; i<test_case; i++) System.out.println(arr[i]); } }

  - 우선 배열의 경우 정적으로 크기를 지정해줘야 합니다. 이 문제에서는 수의 개수가 주어지기 때문에 수의 개수만큼 배열의 크기를 지정하였습니다. 

  - 버블정렬은 정렬할 수의 크기의 -1만큼 회전하기 때문에 배열의 크기를 이용하여 이중루프를 사용했습니다.

  1.2) ArrayList를 이용한 버블 정렬

package sort; import java.util.ArrayList; import java.util.List; import java.util.Scanner; // 백준알고리즘 2750번 : 수 정렬하기 // 버블정렬로 정렬하기 // 문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. // 입력 : 첫째 줄에 수의 개수 N(1<=N<=1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. // 이 수는 절대값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. // 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. // 예제 입력 예제 출력 // 5 1 // 5 2 // 2 3 // 3 4 // 4 5 // 1 public class BubbleSort_ArrayList { // 오름차순 버블 정렬 public void sort(List<Integer> arrlist){ int temp = 0; for(int i=0; i<arrlist.size(); i++){ for(int j=0; j<arrlist.size()-1; j++){ if(arrlist.get(j) > arrlist.get(j+1)){ temp = arrlist.get(j); arrlist.add(j, arrlist.get(j+1)); arrlist.remove(j+1); arrlist.add(j+1, temp); arrlist.remove(j+2); } } } } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); BubbleSort_ArrayList bSort = new BubbleSort_ArrayList(); List<Integer> arrlist = new ArrayList<Integer>(); int test_case = scanner.nextInt(); // 수의 개수 만큼 저장 for(int i=0; i<test_case; i++) arrlist.add(i, scanner.nextInt()); // 버블 정렬 bSort.sort(arrlist); // 정렬된 수 출력 for(Integer list : arrlist) System.out.println(list); } }

  - ArrayList의 경우 크기를 지정하지 않아도 데이터가 추가·삭제될 때마다 자동으로 크기가 할당되기 때문에 따로 크기를 지정할 필요가 없었습니다.

2. 퀵 정렬

  2.1) 배열을 이용한 퀵 정렬

package sort; import java.util.Scanner; // 백준알고리즘 2750번 : 수 정렬하기 // 퀵정렬로 정렬하기 // 문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. // 입력 : 첫째 줄에 수의 개수 N(1<=N<=1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. // 이 수는 절대값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. // 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. // 예제 입력 예제 출력 // 5 1 // 5 2 // 2 3 // 3 4 // 4 5 // 1 public class QuickSort_Array { // 오름차순 퀵 정렬 public void sort(int arr[], int left, int right){ int i = left, j = right, tmp; int piv = arr[(left+right)/2]; // 정렬할 수들의 가운데 값을 피벗으로 지정 while(i <= j){ // 분할 while(arr[i] < piv) // 피벗보다 크면 정렬 i++; while(arr[j] > piv) // 피벗보다 작으면 정렬 j--; if(i <= j){ // 분할을 통해 나눠진 리스트를 정렬 tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; i++; j--; } } // 분할이 끝난 뒤 순환을 통해 정렬 if(left < j) sort(arr, left, j); if(i < right) sort(arr, i, right); } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); QuickSort_Array bSort = new QuickSort_Array(); int test_case = scanner.nextInt(); // 수의 개수 만큼 배열 크기 지정 int arr[] = new int[test_case]; // 수의 개수 만큼 배열에 수 저장 for(int i=0; i<test_case; i++) arr[i] = scanner.nextInt(); // 퀵 정렬 bSort.sort(arr, 0, arr.length-1); // 정렬된 수 출력 for(int i=0; i<test_case; i++) System.out.println(arr[i]); }

  - 퀵 정렬의 핵심 개념은 분할 정복(divide and conquer)과 순환(recursion)입니다.

  - 우선 피벗을 정렬할 수의 가운데 값으로 지정해 주었습니다. 피벗을 기준으로 분할하여 리스트를 나눈 뒤, 재귀호출하여

  정렬하는 방법입니다.

  2.2) ArrayList를 이용한 퀵 정렬

package sort; import java.util.ArrayList; import java.util.List; import java.util.Scanner; // 백준알고리즘 2750번 : 수 정렬하기 // 퀵 정렬로 정렬하기 // 문제 : N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. // 입력 : 첫째 줄에 수의 개수 N(1<=N<=1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. // 이 수는 절대값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. // 출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. // 예제 입력 예제 출력 // 5 1 // 5 2 // 2 3 // 3 4 // 4 5 // 1 public class QuickSort_ArrayList { // 오름차순 퀵 정렬 public void sort(List<Integer> arrlist, int left, int right){ int i = left, j = right, tmp; int piv = arrlist.get((left+right)/2); while(i <= j){ // 분할 while(arrlist.get(i) < piv) i++; while(arrlist.get(j) > piv) j--; if(i <= j){ tmp = arrlist.get(i); arrlist.add(i, arrlist.get(j)); arrlist.remove(i+1); arrlist.add(j, tmp); arrlist.remove(j+1); i++; j--; } } // 순환 if(left < j) sort(arrlist, left, j); if(i < right) sort(arrlist, i, right); } public static void main(String[] args){ Scanner scanner = new Scanner(System.in); QuickSort_ArrayList bSort = new QuickSort_ArrayList(); List<Integer> arrlist = new ArrayList<Integer>(); int test_case = scanner.nextInt(); // 수의 개수 만큼 저장 for(int i=0; i<test_case; i++) arrlist.add(i, scanner.nextInt()); // 퀵 정렬 bSort.sort(arrlist, 0, arrlist.size()-1); // 정렬된 수 출력 for(Integer list : arrlist) System.out.println(list); } }

  - ArrayList의 경우는 배열과 크게 다르지 않습니다. 다만, 고정된 크기가 아니기 때문에 add를 하는 순간 크기도 그만큼 커지므로 추가된 인덱스에 +1 만큼에 위치한 값을 삭제해 주었습니다.