[JAVA] 백준 10814번 나이순 정렬 : 단어정렬

1181번: 단어 정렬

 

1. 문제 추상화

 

알파벳으로 이루어진 단어들을 길이가 짧은 순으로 정렬하시오. 길이가 같으면 알파벳 순으로 정렬하시오.

 

2. 알고리즘

1. HashSet 자료구조

 

예제를 보면 동일한 단어를 입력받으면 출력시, 중복을 제거해주는 것을 확인할 수 있다. 중복제거를 위해 HashSet 자료구조를 사용한다. 

 

2. 정렬 알고리즘

 

Quick, Merge, Heap 정렬 알고리즘을 사용하였다. ( Bubble 정렬은 시간초과가 난다. )

 

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

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

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

 

 

3. 코드

 

1. 중복 제거하기

public static void initializeArr() throws IOException {
		HashSet<String> hs = new HashSet<String>(); // HashSet 생성
		for(int i=0; i < size; i++) {
			stz = new StringTokenizer(bufferedReader.readLine());
			hs.add(stz.nextToken()); // HashSet에 저장하여 중복 제거
		}
		
		Iterator<String> iterator = hs.iterator(); // HashSet 반복자 생성
		arr = new String[hs.size()];
		int i = 0;
		
		while(iterator.hasNext()) {
			arr[i++] = iterator.next(); // 중복이 제거된 데이터를 배열에 저장
		}
	}

 

2. 정렬 알고리즘

 

1. QuickSort

 

	public static void doQuickSort(int leftIndex, int rightIndex) {
		int leftPointer = leftIndex;
		int rightPointer = rightIndex;
		String pivot = arr[(leftIndex + rightIndex)/2];
		
		while(leftPointer <= rightPointer) {
			while(arr[leftPointer].length() <= pivot.length()) {
				if(arr[leftPointer].length() == pivot.length()) {
					if(isSmaller(arr[leftPointer],pivot)) leftPointer++;
					else break;
				}
				else leftPointer++;
			}
			while(arr[rightPointer].length() >= pivot.length()) {
				if(arr[rightPointer].length() == pivot.length()) {
					if(isBigger(arr[rightPointer],pivot)) rightPointer--;
					else break;
				}
				else rightPointer--;
			}
			
			if(leftPointer <= rightPointer) swap(leftPointer++,rightPointer--);
		}
		
		if(leftIndex < rightPointer) doQuickSort(leftIndex,rightPointer);
		if(leftPointer < rightIndex) doQuickSort(leftPointer,rightIndex);
	}
	
	public static void swap(int leftPointer, int rightPointer) {
		String tmp = arr[leftPointer];
		arr[leftPointer] = arr[rightPointer];
		arr[rightPointer] = tmp;
	}
	
	public static boolean isSmaller(String value, String pivot) {
		for(int i =0; i < value.length(); i++) {
			if(value.charAt(i) < pivot.charAt(i)) return true;
			else if(value.charAt(i) > pivot.charAt(i)) return false;
		}
		return false;
	}
	
	public static boolean isBigger(String value, String pivot) {
		for(int i =0; i < value.length(); i++) {
			if(value.charAt(i) > pivot.charAt(i)) return true;
			else if(value.charAt(i) < pivot.charAt(i)) return false;
		}
		return false;
	}

 

2. MergeSort

 

	public static void doMergeSort(int leftIndex, int rightIndex) {
		if(leftIndex < rightIndex) {
			int center = (leftIndex + rightIndex)/2;
			doMergeSort(leftIndex,center);
			doMergeSort(center+1,rightIndex);
			
			doMerge(leftIndex, rightIndex);
		}
	}
	
	public static void doMerge(int leftIndex, int rightIndex) {
		String[] leftArr = new String[rightIndex - leftIndex +1];
		int center = (leftIndex + rightIndex)/2;
		int leftArrSize = 0;
		int leftArrPointer = 0;
		int rightArrPointer = center + 1;
		int arrPointer = leftIndex;
		
		for(int i = leftIndex; i<=center; i++ ) {
			leftArr[leftArrSize++] = arr[i];
		}
		
		for(arrPointer = leftIndex; arrPointer <= rightIndex; arrPointer++) {
			if(leftArrPointer < leftArrSize && rightArrPointer <= rightIndex) {
				if(leftArr[leftArrPointer].length() < arr[rightArrPointer].length()) arr[arrPointer] = leftArr[leftArrPointer++];
				else if(leftArr[leftArrPointer].length() == arr[rightArrPointer].length()) {
					if(isSmaller(leftArr[leftArrPointer],arr[rightArrPointer])) arr[arrPointer] = leftArr[leftArrPointer++];
					else arr[arrPointer] = arr[rightArrPointer++];
				}
				else arr[arrPointer] = arr[rightArrPointer++];
			}else break;
		}
		
		while(leftArrPointer < leftArrSize) {
			arr[arrPointer++] = leftArr[leftArrPointer++];
		}
	}

 

3. HeapSort

	public static void doHeapSort(int leftIndex, int rightIndex) {
		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(i);
			makeHeap(0,i-1);
		}
	}
	
	public static void makeHeap(int pivotIndex, int lastChildIndex) {
		String pivot = 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 {
				if(arr[leftChildIndex].length() > arr[rightChildIndex].length()) childIndex = leftChildIndex;
				else if(arr[leftChildIndex].length() == arr[rightChildIndex].length()) {
					if(isBigger(arr[leftChildIndex],arr[rightChildIndex])) childIndex = leftChildIndex;
					else childIndex = rightChildIndex;
				}
				else childIndex = rightChildIndex;
			}
			
			if(pivot.length() > arr[childIndex].length()) break;
			else if(pivot.length() == arr[childIndex].length()) {
				if(isBigger(pivot,arr[childIndex])) break;
				else arr[parentIndex] = arr[childIndex];
			}
			else arr[parentIndex] = arr[childIndex];
		}
		arr[parentIndex] = pivot;
	}