[24/11/20] 퀵정렬 11004

퀵정렬 구현 결론: high와 low의 교차가 핵심이다. high와 low가 같을때 기준이 아니다. 따라서 low<=high로 low==high일때도 진행해야되는거다.

또한 low는 가만히 있고 high를 계속 땡겼을때도 같을때가 기준이 아닌 교차 기준이니까             while(startIndex+1<=high && arr[pivot]<arr[high]){
                high--;
            }
         

high도 가만히 있고 low를 계속 땡겼을때도 같을때가 기준이 아닌 교차 됐을때가 기준이여서 비록 low가 array 범위 밖으로 나가도 된다.

while(low<=endIndex&& arr[pivot]>arr[low]){
                low++;
            }

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception{
        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());
        st=new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        quickSort(arr,0,N-1,K-1);
        br.close();
    }
    public static void quickSort(int[] arr, int startIndex, int endIndex, int K){
        int pivot = (startIndex+endIndex)/2;
        swap(arr,pivot,startIndex);
        pivot=startIndex;

        int low=startIndex+1;
        int high=endIndex;
        while(low<=high){
            while(startIndex+1<=high && arr[pivot]<arr[high]){
                high--;
            }
            while(low<=endIndex&& arr[pivot]>arr[low]){
                low++;
            }
            if(high>=low){
                swap(arr,high--,low++);
            }
        }
        swap(arr,pivot,high);
        if(high==K){
            System.out.printf("%d",arr[high]);
            return;
        }
        else if(high>K){
            quickSort(arr,startIndex,high-1,K);
        }
        else{
            quickSort(arr,high+1,endIndex,K);
        }


    }
    public static void swap(int[] arr,int p , int q){
        int temp = arr[p];
        arr[p]=arr[q];
        arr[q]=temp;
    }

}

 

진짜 열받는 문제다.

모든 샘플 입력 다 넣어봐도 문제 없이 나오는데 

백준 져지만 들어가면 1%에서 삑난다.

 

아무리봐도 문제될게 없는데 뭐가 문제인지를 모르겠다

import java.util.*;
import java.io.*;

public class Main {
    
    static int a[];
    
    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());
        
        a = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        quickSort(a, 0, n - 1, k - 1);
        System.out.print(a[k - 1]);
    }
    
    public static void quickSort(int a[], int s, int e, int k) {
        if(s < e) {
            int p = partition(a, s, e);
            if(k == p) {
                return;
            }else if(k < p) {
                quickSort(a, s, p - 1, k);
            }else {
                quickSort(a, p + 1, e, k);
            }
        }
    }
    
    public static int partition(int a[], int s, int e) {
        if(s + 1 == e) {
            if(a[s] > a[e]) {
                swap(a, s, e);
            }
            return e;
        }
        
        int m = (s + e) / 2;
        
        swap(a, s, m);
        int p = a[s];
        int i = s + 1;
        int j = e;
        while(i <= j) {
            while(a[j] > p && j >= s + 1) {
                j--;
            }
            while(a[i] < p && i <= e) {
                i++;
            }
            if(i <= j) {
                swap(a, i++, j--);
            }
        }
        
        a[s] = a[j];
        a[j] = p;
        return j;
    }
    
    public static void swap(int a[], int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp; 
    }
}

해설 답은 이거였다.

추가)

내가 보기엔 일단 O(n^2) 짜리 시간복잡도는 버리고 시작하는게 맞다.

그래서 평균에서는 O(nlogn)인 퀵소트를 쓸려고 했는데 내가 구현한건 재귀형식이다.

 

찾아보니 재귀는 매 함수때마다 스택 프레임이 쌓이다보니 기존 반복문보다는 느려질 가능성이 있다.

즉 같은 로직이어도 리턴받으면서 기존 함수를 끝내고 아예 새로운 함수를 호출하는게 재귀함수로 구현한 로직과 같아도 실제 속도면에서는 손해를 본다는 것이다.

 

일단은 재귀를 쓰지 말고 구현해야하는 이유는 알겠다. 

그런데 재귀를 쓰지 않더라도 결국 내가 쓴 코드나 해설 답이나 O(nlogn), 최악에서는 O(n^2)이 나오는건 똑같은데 그러면 내 답에서 오답이 타임아웃땜에 걸리는거면 해설답에서도 타임아웃으로 걸려야되는거 아닌가?

 

내가 구현한 재귀형식은 진짜 퀵소트를 이용하여 고른거고

퀵선택으로 재귀 없이 해당 부분만 선택하는 방법이 더 빠르다고는 한다. (재귀의 유무때문에)

 

내 뇌피셜이라 확실하지는 않다. 근데 퀵선택으로 구현한 것들은 모두 통과되지만 퀵소트만 안되는거보면 재귀의 문제인거 같긴 하다. 

============================================================================================

원인 찾았다.

 

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
    public static void main(String[] args) throws Exception{
        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());
        st=new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        quickSort(arr,0,N-1,K-1);
        br.close();
    }
    public static void quickSort(int[] arr, int startIndex, int endIndex, int K){
        int pivot = (startIndex+endIndex)/2;
        swap(arr,pivot,startIndex);
        pivot=startIndex;

        int low=startIndex+1;
        int high=endIndex;
        while(low<=high){
            while(startIndex+1<=high && arr[pivot]<arr[high]){
                high--;
            }
            while(low<=endIndex&& arr[pivot]>arr[low]){
                low++;
            }
            if(high>=low){
                swap(arr,high--,low++);
            }
        }
        swap(arr,pivot,high);
        if(high==K){
            System.out.printf("%d",arr[high]);
            return;
        }
        else if(high>K){
            quickSort(arr,startIndex,high-1,K);
        }
        else{
            quickSort(arr,high+1,endIndex,K);
        }


    }
    public static void swap(int[] arr,int p , int q){
        int temp = arr[p];
        arr[p]=arr[q];
        arr[q]=temp;
    }

}

퀵정렬로 재귀타서 뽑아오던, 퀵선택으로 재귀 안타고 뽑아오던 둘다 통과는 된다.

 

문제는 범위의 등호이다. 퀵정렬하면서 <= 인지 그냥 < 인지 계속 헷갈렸는데 그게 발목을 잡았다.

 

주의점은 이거다.

 

서로 교차한 후 피봇이랑 교환시켜야하는 것과 피봇이 들어갈 위치에 피봇 값들과 같은 값들이 이미 있는 경우이다.

따라서 swap(arr,high--,low++)와 swap(arr,pivot,high)가 동시에 일어나는 때는 high==low일때이고 

간단하게 생각하면 피봇이 들어갈 위치에 같은 수들이 여러개 없으면 high랑 low랑 서로 교차되게 각자 수행시키다가 교차되면 high쪽이랑 피봇이랑 바꾸면 되고

만약 피봇에 들어갈 위치에 같은 수들이 여러개 있다면 high==low, 또는 high>=low 에서 움직이지 않게 되는데 이때 swap(arr,high--,low++) 으로 바꿔주면서 강제로 high와 low를 땡겨주면 된다.

 

피봇을 중간값으로 잡아도 결국 맨 앞 혹은 맨 뒤로 빼서 퀵정렬 진행할거임. 

high를 먼저 움직이냐 low를 먼저 움직이냐는 상관없고 등호 처리에 유의하기만 하면 됨