[JAVA] 백준 1427번 소트인사이드 : 내림차순 정렬

1427번: 소트인사이드

 

1. 문제 추상화

 

주어진 수의 각 자리수를 내림차순으로 정렬하시오

 

2. 알고리즘

 

1. 수를 문자열로 받는다. 

2. 문자열의 길이만큼 정수 배열을 생성한다.

3. 문자열의 각 문자를 배열에 정수로 저장한다.

4. 내림차순 정렬을 한다. 

 

1번 - 3번까지의 코드는 아래와 같다.

// 1. 수를 문자열로 받기
public static void setInputData() {
	Scanner sc = new Scanner(System.in);
	input = sc.next();
}

// 2. 문자열의 길이만큼 정수배열 생성하기
public static void createArr() {
	arr = new int[input.length()];
}

// 3. 문자열의 각 문자를 정수로 배열에 저장하기
public static void initializeArr() {
	for(int i =0; i< arr.length; i++) {
		arr[i] = input.charAt(i) - '0';
	}
}

 

 

위 과정이 완료되면 배열을 내림차순 정렬을 하면된다. 버블 정렬, 퀵 정렬, 병합 정렬, 카운팅 정렬, 힙 정렬을 사용했다. 정렬 알고리즘은 아래 포스팅에 정리하였다. 아래 포스팅은 모두 오름차순을 기준으로 설명하고 있으니 유념하기를 바란다.

 

 

[알고리즘] 버블정렬 향상 시키기

[알고리즘] 퀵 정렬 (Quick Sort)

[알고리즘] 합병 정렬 ( Merge Sort )

[알고리즘] 힙 정렬 ( Heap Sort )

[JAVA] 백준 10989번 수 정렬하기 3 : 카운팅 정렬 (Counting Sort)

 

 

3. 코드

 

< 버블 정렬 >

 

	public static void doBubbleSort() {
		for(int i =0; i<arr.length-1;i++) {
			int lastExchangeNum = 0;
			int lastExchangeIndex = 0;
			for(int j = arr.length-1; j > i; j--) {
				if(arr[j] > arr[j-1]) {
					swap(j);
					lastExchangeNum++;
					lastExchangeIndex = j-1;
				}
			}
			if(lastExchangeNum == 0) break;
			else i = lastExchangeIndex; 
		}
	}
	
	public static void swap(int value) {
		int tmp = arr[value];
		arr[value] = arr[value-1];
		arr[value-1] = tmp;
	}

 

 

< 퀵정렬 >

 

퀵정렬은 재귀함수가 아닌 Stack을 이용한 반복문을 사용하여 풀었다.

[알고리즘] 퀵정렬 향상시키기 ( 스택 )

 

	public static void doQuickSort(int left, int right) {
		Stack<Integer> leftStack = new Stack<Integer>();
		Stack<Integer> rightStack = new Stack<Integer>();
		
		leftStack.push(left);
		rightStack.push(right);
		
		while(!leftStack.isEmpty()) {
			int leftPointer = left = leftStack.pop();
			int rightPointer = right = rightStack.pop();
			int pivot = arr[(left+right)/2];
			
			while(leftPointer <= rightPointer) {
				while( arr[leftPointer] > pivot ) leftPointer++;
				while( arr[rightPointer] < pivot ) rightPointer--;
				
				if(leftPointer <= rightPointer) {
					swap(leftPointer++,rightPointer--);
				}
			}
			
			if( left < rightPointer ) {
				leftStack.push(left);
				rightStack.push(rightPointer);
			}
			
			if( leftPointer < right ) {
				leftStack.push(leftPointer);
				rightStack.push(right);
			}
		}
	}
	
	public static void swap(int leftPointer, int rightPointer) {
		int tmp = arr[leftPointer];
		arr[leftPointer] = arr[rightPointer];
		arr[rightPointer] = tmp;
	}

 

 

< 병합 정렬 >

 

	public static void doMergeSort(int left, int right) {
		if(left < right) {
			int center = ( left + right )/2;
			
			doMergeSort(left, center);
			doMergeSort(center+1, right);
			
			applyMerge(left,right);
		}
	}
	
	public static void applyMerge(int left, int right) {
		int[] leftArr = new int[right-left+1];
		int center = ( right + left )/2;
		int leftSize = 0;
		int leftPointer = 0;
		int rightPointer = center + 1;
		int arrPointer = left;
		
		for(int i=left; i<=center; i++) {
			leftArr[leftSize++] = arr[i];
		}
		
		for(arrPointer = left; arrPointer <= right; arrPointer++) {
			if(leftPointer < leftSize && rightPointer <= right) {
				arr[arrPointer] = leftArr[leftPointer] > arr[rightPointer] ? leftArr[leftPointer++] : arr[rightPointer++];
			}else {
				break;
			}
		}
		
		while(leftPointer < leftSize) {
			arr[arrPointer++] = leftArr[leftPointer++];
		}
	}

 

 

< 힙 정렬 >

 

	public static void doHeapSort(){
		
		int lastChildIndex = arr.length-1;
		int lastParentIndex = ( lastChildIndex - 1)/2;
		
		for(int i = lastParentIndex; i>=0; i--) {
			makeHeap(i,lastChildIndex);
		}
		
		for(int i = arr.length-1; i>0; i--) {
			swap(0,i);
			makeHeap(0,i-1);
		}	
	}
	
	public static void makeHeap(int pivotIndex, int lastChildIndex) {
		int parentValue = arr[pivotIndex];
		int parentIndex = pivotIndex;
		int childIndex = 0;
		
		for(parentIndex = pivotIndex; parentIndex < (lastChildIndex + 1)/2; parentIndex = childIndex) {
			int leftChildIndex = 2*parentIndex + 1;
			int rightChildIndex = leftChildIndex + 1;
			
			if(rightChildIndex > lastChildIndex) childIndex = leftChildIndex;
			else childIndex = arr[leftChildIndex] < arr[rightChildIndex] ? leftChildIndex : rightChildIndex;
			
			if( parentValue < arr[childIndex] ) break;
			else arr[parentIndex] = arr[childIndex];
		}
		arr[parentIndex] = parentValue;
	}
	
	public static void swap(int root, int lastIndex) {
		int tmp = arr[root];
		arr[root] = arr[lastIndex];
		arr[lastIndex] = tmp;
	}

 

 

<카운팅 정렬>

 

	public static void doCountingSort(){
		int[] countingArr = new int[getMaxValue()+1];
		
		for(int value : arr) {
			countingArr[value]++;
		}
		
		int arrPointer = 0;
		
		for(int i=countingArr.length-1; i >= 0; i--) {
			if(countingArr[i] == 0) continue;
			for( int j = 0; j < countingArr[i]; j++) {
				arr[arrPointer++] = i;
			}
		}
	}
	
	public static int getMaxValue() {
		int max = 0;
		for(int value : arr) {
			if( value > max ) max = value;
		}
		return max;
	}

 

 

< 전체 코드 >

 

각 정렬 알고리즘 코드를 제외한 나머지 부분은 모두 동일하다. 버블 정렬 기준으로 한 전체 코드이다.

import java.util.Scanner;

//버블정렬
public class Main {

	public static String input;
	public static StringBuilder sb;
    	public static int[] arr;

	
	public static void main(String[] args) {
		setInputData(); // 1. 문자열로 수 입력받기
		createArr(); // 2. 문자열 길이로 정수배열 생성하기
		initializeArr(); // 3. 문자열의 각 문자 정수로 배열에 저장하기
		doBubbleSort(); // 4. 배열 내림차순 정렬하기
		printArr(); // 5. 배열 출력하기
	}
	
	public static void setInputData() {
		Scanner sc = new Scanner(System.in);
		input = sc.next();
	}
	
	public static void createArr() {
		arr = new int[input.length()];
	}
	
	public static void initializeArr() {
		for(int i =0; i< arr.length; i++) {
			arr[i] = input.charAt(i) - '0';
		}
	}
	
	public static void doBubbleSort() {
		for(int i =0; i<arr.length-1;i++) {
			int lastExchangeNum = 0;
			int lastExchangeIndex = 0;
			for(int j = arr.length-1; j > i; j--) {
				if(arr[j] > arr[j-1]) {
					swap(j);
					lastExchangeNum++;
					lastExchangeIndex = j-1;
				}
			}
			if(lastExchangeNum == 0) break;
			else i = lastExchangeIndex; 
		}
	}
	
	public static void swap(int value) {
		int tmp = arr[value];
		arr[value] = arr[value-1];
		arr[value-1] = tmp;
	}
	
	public static void printArr() {
		sb = new StringBuilder();
		for( int value : arr) {
			sb.append(value);
		}
		System.out.println(sb.toString());
	}
}