24090번 문제 링크

퀵정렬을 연습하는 문제로 퀵정렬을 복습하기 위해 풀었습니다. 퀵정렬은 pivot(기준값)을 설정하여 start와 end 값을 비교하여 start > pivot 그리고 end < pivot 인 경우, start와 end를 swap 하여 정렬하는 알고리즘 입니다.

여기서 핵심은 pivot과 값을 비교 하는 것이므로 pivot 설정이 알고리즘 수행시간에 큰 영향을 미칩니다.

문제에 해당 로직에 대한 의사코드가 있어 자바 코드로 변환하여 구현하면 크게 어려운 문제는 아닙니다.

초반 로직에 대한 이해도가 떨어져 많이 헤맸던 문제입니다.

😀 성공

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

public class Main{
    static int count;
    static String result;
    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[] arr= new int[N+1];
        
        st = new StringTokenizer(br.readLine());
        br.close();
        for(int i=1; i <= N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        quickSort(arr, 1, N, K);
        
        if(count < K){
            System.out.println(-1);
        }else{
            System.out.println(result);
        }
    }
    
    // 퀵정렬 함수
    static void quickSort(int[] arr, int S, int E, int K){
        if(S < E){
            int pivot = partition(arr,S,E,K); // pivot 설정
            if(pivot < 0) // 성능 개선 - result 초기화 시 정렬 종료
                return;
            quickSort(arr,S,pivot-1,K); // pivot 기준 왼쪽 집합
            quickSort(arr,pivot+1,E,K); // pivot 기준 오른쪽 집합
        }
    }
    
    // 두 집합으로 분할 함수
    static int partition(int[] arr, int S, int E, int K){
        int pivot = arr[E]; // 기준값 선정(끝 값)
        int i = S-1; // i : pivot 기준 작거나 같은수를 앞에서부터 정렬하기 위한 index
        for(int j = S; j < E; j++){ // j : pivot과 비교할 대상 값의 index
            if(arr[j] <= pivot){
                swap(arr,++i,j);
                count++;
                
                if(count == K){
                    result = arr[i] + " " + arr[j];
                    return -1;
                }
            }
        }
        
        // pivot 보다 작거나 같은 수를 정렬한 뒤 정렬된 수의 오른쪽값과 자리를 바꿔준다.
        if(i+1 != E){
            swap(arr,i+1,E);
            count++;
        }
        
        if(count == K){
            result = arr[i+1] + " " + arr[E];
            return -1;
        }
        
        return i+1;
    }

	// 자리 교환 함수
    static void swap(int[] arr,int i, int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}