글 읽기 - 왜 시간초과 나는걸까요...?

aod0326 7년 전 0

퀵소트 방식으로 해서 중간에 K번째 수를 찾았으면

출력하고 flag를 false로 바꿔서 나머지 재귀 함수들이 다 실행되지 않도록 했습니다..

그리고 pivot과 찾고하자는 K를 비교해서 K가 pivot보다 크면 그에 해당하는 재귀함수만 실행하고

다른거는 수행안하도록 했구요..

(아래 코드 보시면 아시겠지만) random함수로 n에 500만, k에 500만 혹은 아무 수 넣고 시간 측정해봤는데

1초도 안나옵니다.. 근데 2%에서 시간초과가 나네요 ㅠㅠ 중간에 논리적으로 틀린 부분이 있는지 먼지 몰겠어요

10번정도 시도했는데 다 시간초과네요 ㅠㅠ

고수분들 도와주시면 감사하겠습니다! ㅠㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	public static boolean flag = true;
	public static long answer;
	public static int partition(long[] a, int k, int start, int end){
		int s = start+1;
		int e = end;
		long pivot = a[start];
		while(true){
			for(;s<=end;s++){
				if(a[s] > pivot)
					break;
			}
			for(;e>start;e--){
				if(a[e] < pivot)
					break;
			}
			if(s >= e){
				swap(a,start,e);
				return e;
			}
			swap(a,s,e);
		}
		
	}
	public static void quickSort(long[] a, int k, int start, int end){
		if(start <= end && flag == true){
			int pivot = partition(a,k,start,end);
			if(pivot == k-1){
				//System.out.println(a[pivot]);
				answer = a[pivot];
				flag = false;
				return;
			}
			if(start == end)
				return;
			if(pivot > k-1)
				quickSort(a,k,start,pivot);
			else
				quickSort(a,k,pivot+1,end);
		}
	}
	public static void swap(long[] a, int x, int y){
		long temp = a[x];
		a[x] = a[y];
		a[y] = temp;
	}
    public static void main(String[] args) throws IOException{
    	long start = System.currentTimeMillis();
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	String[] first = in.readLine().split(" ");
    	int n = Integer.parseInt(first[0]);
    	int k = Integer.parseInt(first[1]);
    	long []a = new long[n];
    	String[] second = in.readLine().split(" ");
    	for(int i=0;i<n;i++){
    		a[i] = Long.parseLong(second[i]);
    	}
//    	Random r = new Random();
//    	for(int i=0;i<n;i++)
//    		a[i] = r.nextLong()%2000000001-1000000000;
    	quickSort(a,k,0,n-1);
    	System.out.println(answer);
    	long end = System.currentTimeMillis();
//    	System.out.println("실행시간:"+ (end-start)/1000.0+" sec");
    }
}

bupjae 7년 전 0

pivot 를 start 점으로 하셨는데, 이 경우 배열이 이미 정렬 (또는 역정렬) 되어 있을 경우 효율이 매우 떨어집니다.

aod0326 7년 전 0

백준님 퀵소트 소스가 pivot을 중앙에 잡은거라서 그대로 써서 해봤는데도

2%에서 멈추네요....................................................................ㅠㅠㅠㅠㅠ

뭘 건드려야 대는지 모르겠어요 ㅠㅠ

import java.util.*;
public class Main {
	public static boolean flag = true;
	public static long answer = 0;
	public static int partition(long[] a, int k, int start, int end){
		int pivot = (start + end)/2;
		long pivotValue = a[pivot];
		swap(a,pivot,end);
		int storeIndex = start;
		for(int i=start;i<end;i++){
			if(a[i] < pivotValue){
				swap(a,i,storeIndex);
				storeIndex += 1;
			}
		}
		swap(a,storeIndex,end);
		return storeIndex;
	}
	public static void quickSort(long[] a, int k, int start, int end){
		if(start <= end && flag == true){
			int pivot = partition(a,k,start,end);
			if(pivot == k-1){
				flag = false;
				answer = a[pivot];
				return;
			}
			if(start == end)
				return;
			quickSort(a,k,start,pivot-1);
			quickSort(a,k,pivot+1,end);
		}
	}
	public static void swap(long[] a, int x, int y){
		long temp = a[x];
		a[x] = a[y];
		a[y] = temp;
	}
    public static void main(String[] args) throws IOException{
    	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    	String[] first = in.readLine().split(" ");
    	int n = Integer.parseInt(first[0]);
    	int k = Integer.parseInt(first[1]);
    	long []a = new long[n];
    	String[] second = in.readLine().split(" ");
    	Random r = new Random();
    	for(int i=0;i<n;i++){
    		a[i] = Long.parseLong(second[i]);
    	}
    	quickSort(a,k,0,n-1);
    	System.out.println(answer);
    }
}

aod0326 7년 전 0

아.... 500만개 숫자 입력받는게 문제였네요..

in.readLine().split(" ");해서 받았는데 이게 문제였어요..

StringTokenizer로 하니까

그냥 Arrays.sort()하고나서 k번째꺼 출력해도 시간안에 출력되네요...

이런 허무한..

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

문제

문제

출처

ICPC

왜 시간초과 나는걸까요...?

aod0326 7년 전 0

bupjae 7년 전 0

aod0326 7년 전 0

aod0326 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말