[백준] 11004번 K번째 수 - 퀵정렬 / 오름차순 정렬

문제

 

 

My Code

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

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N;
int findindex;
int [] input = new int[2];
int start, end, pivot;

StringTokenizer st = new StringTokenizer(bf.readLine());
for (int i = 0; i<2; i++)
{
input[i] = Integer.parseInt(st.nextToken());
}
N = input[0];
findindex = input[1];

int [] numArray = new int[N];
st = new StringTokenizer(bf.readLine());
for (int i = 0; i<N; i++)
{
numArray[i] = Integer.parseInt(st.nextToken());
}

start = 0;
end = 1;
pivot = 2;
int sameindex = 0;
int index = N-1;
while (pivot != numArray[0]){
start = numArray[0];
end = numArray[index-1];
pivot = numArray[index];

for(int i = 0; i < index-1; i++){
if(start < pivot) start = numArray[i+1];
if (end > pivot) end = numArray[index-2 -i];
if( start > pivot && end < pivot) {
numArray[i] = end;
numArray[index-1]= start;
start = numArray[i+1];
end = numArray[index-2 -i];
}
sameindex = i + 1;
if (start == end){
break;
}
}

if (start < pivot) {
int pivot2 = pivot;
for (int i = index; i > sameindex+1; i--){
numArray[i] = numArray[i-1];
}
numArray[sameindex+1] = pivot2;
}
else {
int pivot2 = pivot;
for (int i = index; i > sameindex-1; i--){
numArray[i] = numArray[i-1];
}
numArray[sameindex-1] = pivot2;
}
index = sameindex;
}

System.out.println(numArray[findindex-1]);
}
}

결과

결과가 나오긴 하는데 다른 배열로 응용하면 다르게 결과가 나와서 

코드가 잘못된 것 같다고 느꼈다...

 

 

문제의 핵심 및 알게된 점

퀵정렬의 원리를 이용해서 효율적인 풀이가 가능하다.

pivot값을 배열의 중간 값으로 설정하여 

pivot == k  ->  return k; 

pivot > k   ->  s ~  pivot-1까지만 탐색

pivot < k  -> pivot+1 ~ e까지만 탐색 

위와 같이 분배할 수 있기 때문이다.

 

 

참고 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N;
        int K;
        int [] input = new int[2];
        int S, E, P;

        StringTokenizer st = new StringTokenizer(bf.readLine());
        for (int i = 0; i<2; i++)
        {
            input[i] = Integer.parseInt(st.nextToken());
        }
        N = input[0];
        K = input[1];

        int [] A = new int[N];
        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i<N; i++)
        {
            A[i] = Integer.parseInt(st.nextToken());
        }

        quickSort(A, 0, N-1, K-1);
        System.out.println(A[K-1]);
    }

    private static int quickSort(int[]  a, int s, int e, int k) {
        int pivot = partition(a, s, e);
        if (pivot == k) return k;
        else if (k < pivot) {
            quickSort(a, s, pivot-1, k);
        }
        else {
            quickSort(a, pivot+1, e, k);
        }
        return pivot;
    }

    private 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 pivot = a[s];
        int i = s+1;
        int j = e;

        while (i <= j){
            while (pivot < a[j] && j>0) j--;
            while (pivot > a[i] && i < a.length-1) i++;
            if (i <= j) swap(a, i++, j--);
        }
        a[s] = a[j];
        a[j] = pivot;
        return j;
    }
    private static void swap(int[] a, int s, int e){
        int temp = a[s];
        a[s] = a[e];
        a[e] = temp;
    }
}

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA