Algorithm/백준 문제풀이
백준 2751 - 수 정렬하기 2(자바 구현)
leedg36
2021. 5. 10. 22:51
반응형
public class Q_2751 {
static int[] sortArray;
//배열 쪼개기
public static void mergeSort(int[] array, int start, int end) {
if(start < end) {
int middle = (start+end)/2;
mergeSort(array, start, middle);
mergeSort(array, middle+1, end);
merge(array, start, middle, end);
}
}
//배열 합치기
public static void merge(int[] array, int start, int middle, int end) {
int i = start;
int j = middle+1;
int k = start;
while(i <= middle && j <= end) {
if(array[i] <= array[j]) {
sortArray[k] = array[i++];
}else {
sortArray[k] = array[j++];
}
k++;
}
//정렬 후, 남은 데이터 추가
if(i > middle) {
for(int l=j; l <= end; l++) {
sortArray[k] = array[l];
k++;
}
}else {
for(int m=i; m <= middle; m++) {
sortArray[k] = array[m];
k++;
}
}
//정렬된 배열 삽입
for(int n=start; n<=end; n++ ) {
array[n] = sortArray[n];
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer sb = new StringBuffer();
int N = Integer.parseInt(br.readLine().trim());
sortArray = new int[N];
int[] array = new int[N];
for(int i=0; i < N; i++) {
array[i] = Integer.parseInt(br.readLine().trim());
}
mergeSort(array, 0, array.length-1);
for (int i = 0; i < array.length; i++) {
sb.append(array[i]+"\n");
}
System.out.print(sb);
}
}
반응형