반응형
11004번 K번째 수
스터디에서 진행한 퀵정렬문제
퀵정렬부턴 구현이 아직 어색해서 힘들었는데, 더 힘들었던건.. 좌측피벗정렬만 고집하다가 시간을 많이 사용했다.
좌측피벗 저격인지 원래 좌측보다 중간이 좋은지 모르겠는데 일단 풀리긴 했음...
--------
hint
중간피벗 퀵정렬을 사용하자...
--------
Solution
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 | import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Scanner; import java.util.StringTokenizer; public class Main{ //중간 피벗 퀵정렬 //11004 https://www.acmicpc.net/problem/11004 public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int[] a = new int[n]; st = new StringTokenizer(br.readLine()); for(int i = 0; i < n; i++){ a[i] = Integer.parseInt(st.nextToken()); } //구현부 qSort sort = new qSort(); qSort.middleQuickSort(a, 0, a.length - 1); System.out.println(a[k-1]); } } class qSort{ static void middleQuickSort(int[] a, int left, int right){ if(left >= right){ return ; } int pivotIndex = partition(a, left, right); middleQuickSort(a, left, pivotIndex - 1); middleQuickSort(a, pivotIndex, right); } static int partition(int[] a, int left, int right){ int pivot = a[(left+right) / 2]; while(left <= right){ while(a[left] < pivot){ left++; } while(a[right] > pivot){ right--; } if(left <= right){ swap(a, left, right); left++; right--; } } return left; } static void swap(int[] a, int b, int c){ int temp = a[b]; a[b] = a[c]; a[c] = temp; } } | cs |
실행시간 - 1708ms
실패한 실행코드(좌측피벗 퀵정렬)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | public class Main{ // 이건 시간초과로 안됨 좌측피벗정렬임. public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //Scanner sc = new Scanner(System.in); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int[] a = new int[n]; st = new StringTokenizer(br.readLine()); for(int i = 0; i < n; i++){ a[i] = Integer.parseInt(st.nextToken()); } //구현부 quickSort sort = new quickSort(); sort.sort(a, 0, a.length-1); System.out.println(a[k-1]); // for (int num:a) { // System.out.println(num); // } } } class quickSort{ void sort(int[] a, int left, int right){ if(left >= right){ // 스택오버플로우방지 return ; } int pivot = partition(a, left, right); sort(a, left, pivot - 1); sort(a, pivot + 1, right); } int partition(int[] a, int left, int right){ int pivot = a[left]; int pivotIndex = left; while(left < right) { while (a[right] > pivot && left < right) { right--; } while (a[left] <= pivot && left < right) { left++; } swap(a, left, right); } swap(a, pivotIndex, left); return left; } void swap(int[] a, int i, int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } } | cs |
반응형
'공부 > Algorithm' 카테고리의 다른 글
| 백준 24444번 너비 우선 탐색 1 자바로 풀어 본 짧은 글 (0) | 2023.04.30 |
|---|---|
| 백준 13023번 ABCDE 자바로 풀어 본 짧은 글 (0) | 2023.04.22 |
| 백준 2164번 카드2 자바로 풀어 본 짧은 글 (0) | 2023.03.18 |
| 24060번 알고리즘 수업 - 병합 정렬 1 자바로 풀어 본 짧은 글 (0) | 2023.02.04 |
| 1920번 수 찾기 자바로 풀어 본 짧은 글 (0) | 2023.01.14 |