수 정렬 문제이다. 퀵정렬을 공부한 김에 관련 문제에 대해서 풀어 보았다.
이문제를 푸는 방법에는 여러가지 방식이 있는데, 나는 공부한 퀵정렬을 활용 했다.
<실행 코드> - JAVA import java.util.*; public class QuickSort{ private static void quickSort(int[] arr) { //quickSort 함수 선언 quickSort(arr,0,arr.length-1); //정렬을 할 배열을 받아서 시작 위치와 끝나는 위치를 정하기 } //start, end, 파티션을 나눌 범위를 설정해 인자로 받음 private static void quickSort(int[] arr, int start, int end) { //재귀함수를 본격적으로 호출 int part2 = partition(arr,start,end); //해당 배열의 파티션을 나누고 값을 받아오기 if(start < part2-1){ quickSort(arr,start, part2-1); } if(part2<end){// quickSort(arr,part2, end);// } } private static int partition(int[] arr, int start, int end) { //시작은 오른쪽 파티션의 시작값 끝나는 지점은 처음에 받은 배열에 끝나는 값으로 호출 int pivot = arr[(start + end)/2]; //인덱스를 받고, 피벗은 중간값으로 설정 while(start <= end) {// 시작과 끝이 같은 동안만 반복 while(arr[start] < pivot)start++; while(arr[end] > pivot) end--; if(start <= end) {// end와 시작점이 만났는지 확인 swap (arr, start, end); //각각을 swap함 start++; end--; / } } return start; } private static void swap(int[] arr, int start, int end) { //swap 함수 정의 int tmp = arr[start];//임시공간에 잠시 담고 arr[start] = arr[end]; // 옮기고 arr[end] = tmp; // 임시 공간에 저장 했던걸 옮긴데이터에 복사 } private static void printArray(int[] arr){//배열 출력 for(int data : arr) { System.out.println(data ); } } public static void main(String[] args) { Scanner sc =new Scanner(System.in); //스캐너 객체 생성 int co = sc.nextInt(); // 입력 받고자 하는 수의 갯수를 입력 받아 변수에 저장 int[] arr = new int[co]; // 입력 받은 정수를 저장할 배열 생성 for (int i=0; i<co; i++) { arr[i] = sc.nextInt(); } quickSort(arr);// QuickSort 정렬하기 printArray(arr);//정렬 후 출력 } } |
저번의 코드와 차이점 있다면, 크게 2가지 이다.
한개는 저번에는 배열이 주어졌을 때, 퀵정렬을 했다면 이번에는 값을 입력 받아서 정렬을 해주었다.
두번째는 백준의 특성상 출력 값이 그대로 여야 해서 콤마를 지웠다.
문제는 사실 브론즈 난이도 2로 다른 방법으로 간단하게 해결 할 수 있지만, 공부한 내용을 이용 하기 위해 퀵정렬로 문제를 해결했다.
퀵정렬 공부 내용은 다음과 같다.
https://tae-coding.tistory.com/25?category=1059563
[Algorithm] 퀵 정렬 (Quick Sort)1_JAVA
일반적으로 가장 많이 사용 되는 퀵정렬(Quick Sort)에 대해 공부해 보자. 퀵정렬은 이럼텨렴 졍렬 속도가 매우 빠른 것에서 착안하여 알고리즘 개발자 찰스 앤터니 리터드 호어(C. A. R. Hoare)가 착안
tae-coding.tistory.com
https://tae-coding.tistory.com/28?category=1059563
[Algorithm] 퀵 정렬 (Quick Sort)2_JAVA
계속 해서 퀵정렬을 살펴보자. 우선 앞에서 배운 내용을 바탕으로 퀵정렬을 구현해보면 아래와 같다. [퀵정렬 구현] <실행코드> - JAVA import java.util.*; public class QuickSort{ private static..
tae-coding.tistory.com
'포트폴리오 > 백준 알고리즘' 카테고리의 다른 글
[5일차] 백준 class1_1000,1001,1008 (0) | 2022.07.31 |
---|---|
[4일차] 백준_2875 (0) | 2022.07.29 |
[3일차] 백준_17608 (0) | 2022.07.29 |
[2일차] 백준 15953 (0) | 2022.07.28 |
[1일차] 백준_2739 (0) | 2022.07.27 |