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

Study/알고리즘

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

연계중 2017. 10. 22. 04:18

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

자료구조는 배열과 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;

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 만큼에 위치한 값을 삭제해 주었습니다.

저작자표시 (새창열림)