글 읽기 - JAVA 시간초과 문제

wewe1008 4년 전 0

입력시간 줄이려고 BufferedReader 사용했는데도 시간초과가 뜨네요 ㅠㅠ

Arrays.sort를 쓰고는 절대 풀지 못하는 문제인가요?

어느부분에서 시간초과인지 알고싶습니다.

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

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		int line = Integer.parseInt(st.nextToken());
		int seq = Integer.parseInt(st.nextToken());
		
		int[] num = new int[line];
		
		st = new StringTokenizer(br.readLine());
		
		for(int i=0; i<line; i++) {
			num[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(num);
		bw.write(num[seq-1]+"");
		bw.flush();
	}
}

lim551 4년 전 0

O(n)에 k번째 원소를 찾을 수 있는 quick select 알고리즘을 사용하라고 만든 문제입니다.

자바로 제출해본 적이 없어 입출력 병목인지는 모르겠는데 아마 500만까지는 buffered reader 사용하면 괜찮지않나 싶습니다.

우선 위에서 말한 퀵 셀렉트 알고리즘 찾아보시는걸 추천드립니다.

c++에는 stl로 구현이 돼있는데 자바에서는 아마 직접 구현하셔야 할겁니다.

djm03178 4년 전 0

Arrays.sort(int[])는 O(N^2)입니다.

https://www.acmicpc.net/board/view/34488

https://blog.kyouko.moe/29?category=767011

lim551 4년 전 0

자바로 푸신 분이 두 분 계시는데 모두 버퍼리더 사용하고 sort해서 풀셨는데 서버 상태가 좋으면 그렇게 해도 풀리긴 하는 것 같습니다.

특이한건 두 분 모두 배열의 원소 타입을 primitive 타입이 아닌 래퍼 클래스로 썼다는건데, 이게 상관 있는지는 모르겠습니다.

ho94949 4년 전 2

@lim551

네 상관이 있습니다. 래퍼 클래스를 사용한 Integer[] 의 정렬은 Collections.sort의 병합정렬을 사용하고, 시간이 O(N log N)이고, int[]의 정렬은 DualPivotQuicksort를 사용하고, 최악의 경우 시간이 O(N^2)을 걸립니다. 위에 올린 게시글의 데이터를 받아서 로컬에서 실행해보시면 됩니다.