글 읽기 - (자바) PivotSort + StringToken으로 구현했는데 시간초과....

leejy19908036 5년 전 0

(자바) PivotSort + StringToken으로 구현했는데 시간초과가 계속 나네요...

그냥 Arrays.sort 로 하면 '성공'인데..

피봇으로 구현하면 더빠르다고 해서 구현 실행하는데..

Scanner도 느릴수 있다고 해서 BufferedReader랑 StringToken 다 사용하는데도

시간초과가 왜 뜰까요...?

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

public class Main {
	public static void main(String args[]) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine()," ");
		int n = Integer.parseInt(st.nextToken()); // N개
		int k = Integer.parseInt(st.nextToken()); // k번째
		int arr[] = new int[n];
		
		st = new StringTokenizer(br.readLine()," ");
		for (int i = 0; i < n; i++)
				arr[i] = Integer.parseInt(st.nextToken());
		

		quickSort(arr, 0, arr.length - 1);

		System.out.println(arr[k - 1]);
	}

	static void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int pivotNewIndex = partition(arr, left, right);
			quickSort(arr, left, pivotNewIndex - 1);
			quickSort(arr, pivotNewIndex + 1, right);
		}
	}

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

		int pivot = arr[(left + right) / 2];

		while (left < right) {
			while ((arr[left] < pivot) && (left < right))
				left++;
			while ((arr[right] > pivot) && (left < right))
				right--;

			if (left < right) {
				int temp = arr[left];
				arr[left] = arr[right];
				arr[right] = temp;
			}
		}

		return left;
	}
}

kimsy96 5년 전 0

이분탐색코드가 최악의 경우O(n^2) 인데 코드를 짤 때

저런식으로 pivot을 대충? 구현하면(왼쪽이나 오른쪽이나 가운데..?)

최악의 경우가 발생할가능성이 큽니다.

보통은그냥 그 언어에서 제공하는함수를쓰는데

직접만들어쓰는게 더 빠르다는건.. 잘모르겠네요

isku 5년 전 0

An이 같은 수가 있을 수 있습니다.

그 부분이 처리되지 않았네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(자바) PivotSort + StringToken으로 구현했는데 시간초과....

leejy19908036 5년 전 0

kimsy96 5년 전 0

isku 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말