반응형

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
반응형
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
public class Main {
    public static void printArray(int[] a) {
        for(int i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }
    
    public static int divideArray(int[] a, int head, int tail) {
        int left, right, temp;
        left = head + 1;
        right = tail;
        
        while(true) {
            while(left < tail && a[head] > a[left]) {
                left++;
            }
            
            while(a[head] < a[right]) {
                right--;
            }
            
            if(left >= right) {
                break;
            }
            
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            
            left++;
            right--;
            
        }
        temp = a[head];
        a[head] = a[right];
        a[right] = temp;
        
        return right;
        
    }
    
    public static void sortArray(int[] a, int start, int end) {
        int pivot;
        
        if(start < end) {
            pivot = divideArray(a, start, end);
            
            sortArray(a, start, pivot - 1);
            
            sortArray(a, pivot + 1, end);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] a = new int[n];
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        //printArray(a);
        
        sortArray(a, 0, a.length - 1);
        
        printArray(a);
        
    }
}
cs

O(nlogn)의 속도가 평균적이고, 최악에는 O(n^2)의 시간복잡도가 나오기도 한다.

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
이진 탐색  (0) 2023.01.07

+ Recent posts

티스토리툴바