글 읽기 - 시간초과 해결 방법

ljo950924 4년 전 0

중간값과 맨 처음 값의 위치를 바꿔서

중간값을 피벗으로 사용할 수 있도록 하여

배열이 정렬되어있을 경우에 시간초과가 발생하지 않도록 해주었습니다.

하지만 여전히 시간초과가 생기는데

어떻게 해야 시간을 더 줄일 수 있나요?

아니면 그냥 힙 정렬을 사용해야하는 건가요??

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		
		String[] tmp = bf.readLine().split(" ");
		int n = Integer.parseInt(tmp[0]);
		int k = Integer.parseInt(tmp[1]);
		
		int[] a = new int[n];
		StringTokenizer 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]);
		
	}
	
	static void quickSort(int[] a, int start, int end, int k) {
		// 중간값과 맨 앞에 값 위치 변경
		int tmp = a[(start+end)/2];
		a[(start+end)/2] = a[start];
		a[start] = tmp;
		
		int pivot = start;
		int i = start+1;
		int j = end;
		
		// 엇갈리기 전까지
		while(i<=j) {
			// 큰 값 찾기
			while(i<=end && a[pivot]>=a[i]) {
				i++;
			}
			// 작은 값 찾기
			while(j>start && a[pivot]<=a[j]) {
				j--;
			}
			
			if(i<j) {
				tmp = a[i];
				a[i] = a[j];
				a[j] = tmp;
			} else {
				tmp = a[pivot];
				a[pivot] = a[j];
				a[j] = tmp;
			}
		}
		
		if(j==k) {
			return;
		}
		else if(j>k) {
			quickSort(a, start, j-1, k);
		} else {
			quickSort(a, j+1, end, k);
		}	
	}
}

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

문제

문제

출처

ICPC

시간초과 해결 방법

ljo950924 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말