BJ_S5_11004_K번째 수 - Java

[문제링크]

https://www.acmicpc.net/problem/11004

11004번: K번째 수

---

[문제]

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

---

[입력]

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

 

---

[출력]

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

---

[예제 입력 1]

5 2
4 1 2 3 5

---

[예제 출력 1]

2

 

---

[설명]

이 문제는 퀵소트 문제이다.

퀵소트를 이용하여 풀어야하는 문제인데, 왜인지 퀵소트를 사용하여 풀어도 시간초과가 나온다.오히려 BufferedReader를 사용하여 Arrays.sort를 돌려버리면 통과가 된다.오답이 왜 시간초과가 나오는지 아시는분은 댓글로 남겨주시면 감사하겠습니다..

 

<오답>

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

public class Main {

	static int[] arr;
	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());
		arr=new int[N];
		int K=Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		System.out.println(quick_sort(arr, 0, N-1,K));
	}

	private static int quick_sort(int[] arr, int start, int end, int k) {
		
		if(start<end) {
			int pivot = partition(arr,start,end);
			if(k == pivot-(start-1))return arr[pivot];
			if(k<pivot-(start-1)) return quick_sort(arr,start,pivot-1,k);
			else return quick_sort(arr,pivot+1,end,k);
		}
		else return arr[start];
	}

	private static int partition(int[] arr, int start, int end) {
		int pivot = arr[0];
		int left=start;
		int right=end;
		while(left < right) {
			while(left<right && arr[left]<=pivot) {
				left+=1;
			}
			while(pivot<arr[right]) {
				right-=1;
			}
			swap(arr,left,right);
		}
		swap(arr,start,right);
		
		return left;
	}

	private static void swap(int[] arr2, int left, int right) {
		int temp = arr[left];
		arr[left] = arr[right];
		arr[right] = temp;
	}
}

 

백준 알고리즘 11004번 JAVA풀이

 

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

public class Main {

	static long[] arr;
	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());
		arr=new long[N];
		int K=Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) {
			arr[i]=Long.parseLong(st.nextToken());
		}
		
		Arrays.sort(arr);
		System.out.println(arr[K-1]);
	}
}

 

 

 

궁금하신 부분이나 부족한 점은 댓글로 알려주시면 감사하겠습니다.