[백준/10989] 수 정렬하기3 - 자바

문제

 

코드

package sort;

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

public class Q10989 {
	//수 정렬하기3
	
	static int[] arr;
	static int[] sorted;
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int N = Integer.parseInt(bf.readLine());
		arr = new int[N];
		sorted = new int[N];
		int i;
		for(i=0;i<N;i++) {
			arr[i] = Integer.parseInt(bf.readLine());
		}
		//함수사용
		//Arrays.sort(arr);
        //병합정렬(오답)
		//mergeSort(0,arr.length-1);
        //퀵정렬
		quickSort(0,arr.length-1);
		
		for(i=0;i<arr.length;i++) {
			bw.write(String.valueOf(arr[i])+"\n");
		}
		
		bf.close();
		bw.flush();
		bw.close();
	}
	
	public static void quickSort(int x,int y) {
		
		int left = x, right = y, pivot = arr[(x+y)/2], temp;
		
		do{
			while(pivot > arr[left]) left++;
			while(pivot < arr[right]) right--;
			if(left <=right) {
				temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
				left++;
				right--;
			}
		}while(left <= right);
		
		if(x < right) quickSort(x,right);
		if(y > left) quickSort(left,y);
		
	}
	
	public static void mergeSort(int x,int y) {
		
		if(x<y) {
			int mid = (x+y)/2;
			mergeSort(x,mid);
			mergeSort(mid+1,y);
			merge(x,mid,y);
		}
	}
	
	public static void merge(int x,int mid,int y) {
		
		int i = x;
		int j = mid+1;
		int k = x;
		
		while(i<=mid && j<=y) {
			if(arr[i] < arr[j]) {
				sorted[k] = arr[i];
				i++;
			}else {
				sorted[k] = arr[j];
				j++;
			}
			k++;
		}
		
		if(i>mid) {
			for(int t=j;t<=y;t++) {
				sorted[k] = arr[t];
				k++;
			}
		}else {
			for(int t=i;t<=mid;t++) {
				sorted[k]=arr[t];
				k++;
			}
		}
		
		for(int t=x;t<y;t++) {
			arr[t] = sorted[t];
		}
		
	}

}

세가지 방법으로 풀어봤습니다.

첫번째로 내장함수인 Arrays.sort() 퀵정렬인데 조금 다른 퀵정렬을 사용한다고 어렴풋이 기억합니다. 정답이었구요.

 

두번째로 병합정렬로 풀이해봤습니다. 이유는 모르겠고 시간초과가 나오더라구요..

 

세번째로 퀵정렬로 풀이했습니다. 정답이 나왔어요. 전에 했던 방식은 알고리즘 공부하고 있는 '동빈나'님의 코드를 따라한거였는데 이번엔 https://hahahoho5915.tistory.com/9 여기 주소의 코드를 보고 따라했습니다. 저는 이미 공부를 했었어서 그런지 이 코드도 이해하기 어렵지 않았고 오히려 이해가 빠르게 됐어요!

 

감사합니다!