글 읽기 - java 이보다 더 빨리 할 수 있나요? 도와주세요 ㅠㅠ!!

haeran97 4년 전 0

Arrays.sort()로 되나 싶어서 입출력만 빨리 해봤는데 안되고

퀵 셀렉션을 해봤는데 피봇을 인덱스의 중간값으로 줘서 안되나 싶어서 랜덤으로 줘봤는데도 안되네요

이보다 더 빨리 할 수 있나요?ㅠ.ㅜ 아무리 해도 96%에서 시간초과가 나네요..

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Random;
//import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		BufferedReader reader= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st1 = new StringTokenizer(reader.readLine());
		
		int size = Integer.parseInt(st1.nextToken());
		int[] arr = new int[size];
		
		
		int target = Integer.parseInt(st1.nextToken());
		StringTokenizer st2 = new StringTokenizer(reader.readLine());
		
		for(int i=0; i<size; i++)
			arr[i]=Integer.parseInt(st2.nextToken());
		
//		reader.close();
//		Arrays.sort(arr); 이거 넘 느린가봐..
		
		//퀵 셀렉트 
		int from = 0, to = arr.length - 1;
		Random random = new Random();
		 // if from == to we reached the kth element
		 while (from < to) {
		  int r = from, w = to;
//		  int mid = arr[(r + w) / 2];
		  int mid = arr[random.nextInt(w+1)];
		 
		  // stop if the reader and writer meets
		  while (r < w) {
		 
		   if (arr[r] >= mid) { // put the large values at the end
		    int tmp = arr[w];
		    arr[w] = arr[r];
		    arr[r] = tmp;
		    w--;
		   } else { // the value is smaller than the pivot, skip
		    r++;
		   }
		  }
		 
		  // if we stepped up (r++) we need to step one down
		  if (arr[r] > mid)
		   r--;
		 
		  // the r pointer is on the end of the first k elements
		  if (target-1 <= r) {
		   to = r;
		  } else {
		   from = r + 1;
		  }
		 }
		
//		System.out.println(arr[target-1]);
		bw.write(Integer.toString(arr[target-1]));
		bw.flush();
		bw.close();
	}

}

chogahui05 4년 전 1

COUNT SORT로 찾는 건 어떠한가요?

저게 500만까지 들어오다 보니까. 조금이라도 호출 깊이가 깊어지면 초과가 나는 거 같기는 한데..

random.nextInt(w+1); 가

0부터 w사이의 랜덤값을 추출하는 걸로 알고 있는데..

r부터 w까지 중에서 random하게 뽑아야 하나요? 0부터 w까지 random하게 뽑아야 하나요?

만약에 후자라면 38번째 줄이 비효율적으로 동작하게 되겠는데.. 테스트를 더 해 보니까.

n = 5x10^6, k = 10^6이고

임의의 1<=i,j<=5x10^6에 대해서, A(i) = A(j)인 경우에 Kill 나네요. 이 경우에 잘 처리해 보세요.

chogahui05 4년 전 1

A(i) = A(j)인 경우에, 한 쪽으로 치우치는 상황을 회피하기 위해서는

예를 들자면

5, ... , 5

이렇게 나온 경우에. 일단 Random하게 뽑아도 5니까.

5보다 확실하게 작은 녀석하고, 5보다 확실하게 큰 녀석하고 뽑습니다. 이들을 각각 SMALL, LARGE라고 하면

SMALL하고 LARGE하고 저장을 해 놓은 다음에 (예를 들어 SMALL에 0개, LARGE에 0개 있었다고 치면)

전체 갯수가 t개라고 했을 때

partition이 될 수 있는 범위는 0 ~ t-0까지입니다. 고로, 이 범위 내에서 아무 거나 고르면 되는데

이왕이면 depth가 적게 호출되는 쪽인 t/2를 고르는 게 이득이겠져. 그런 식으로 처리를 잘 하시면 될 듯 싶습니다.

haeran97 4년 전 0

답변 정말 감사합니다. 확인한지는 좀 됐는데 바빠서 문제 다시풀 생각을 안하고 있었는데

chogahui05님 답변보니까 갑자기 공부하고 싶어지네요 열심히 해보겠습니다~

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

문제

문제

출처

ICPC

java 이보다 더 빨리 할 수 있나요? 도와주세요 ㅠㅠ!!

haeran97 4년 전 0

chogahui05 4년 전 1

chogahui05 4년 전 1

haeran97 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말