문제19번

질문할 것 ) 왜 numberformatException이 뜨지? → br.readline으로 받으면 안됐음.

public class Main {
    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];
        
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        
        System.out.println(quickSelect(arr, 0, N-1, K-1));
    }

    static int quickSelect(int[] arr, int left, int right, int K) {
        if(left <= right) {
            int pivot = partition(arr, left, right);
            if(pivot == K) return arr[K];
            else if(pivot < K) return quickSelect(arr, pivot+1, right, K);
            else return quickSelect(arr, left, pivot-1, K);
        }
        return -1;
    }

    static int partition(int[] arr, int left, int right) {
        int pivot = arr[right];  
        int i = left - 1;
        
        for(int j=left; j<right; j++){
            if(arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i+1, right);
        return i+1;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

2번째 try..

public class Main {
    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];

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

        System.out.println(quickSelect(arr, 0, N-1, K-1));

        br.close();
    }

    static int quickSelect(int[] arr, int left, int right, int K) {
        if(left <= right) {
            int pivot = partition(arr, left, right);
            if(pivot == K) return arr[K];
            else if(pivot < K) return quickSelect(arr, pivot+1, right, K);
            else return quickSelect(arr, left, pivot-1, K);
        }
        return -1;
    }

    static int partition(int[] arr, int left, int right) {

        int pivotIdx = left + (right - left)/2;

        int pivot = arr[pivotIdx];
        int i = left - 1;

        for(int j=left; j<right; j++){
            if(arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i+1, right);
        return i+1;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

20번

병합정렬

package day4.B2751;

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        // min힙만드러
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 힙 추가
        for (int i = 0; i < n; i++) {
            minHeap.add(Integer.parseInt(br.readLine()));
        }

        // 힙에서 꺼내고 동시에 출력하기.
        while (!minHeap.isEmpty()) {
            bw.write(minHeap.poll() + "\\n");
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

21번

https://tussle.tistory.com/1102

22번