글 읽기 - 10816 시간초과 도와주세요 ㅜㅜ

quf9484 4년 전 0

혼자 도저히 해결을 못해서 질문을 올립니다 ㅜㅜ

질문에 있는 같은 수가 나오는 경우를 처리 했는데도 시간초과가 나오는데 어느 부분이 시간을 많이 잡아먹는건가요?

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int[] arr;
	static int[] res;
	static int[] chk = new int[20000001];
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		arr = new int[N];
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
		 
		Arrays.sort(arr);
		
		int M = in.nextInt();
		res = new int[M];
		for(int i = 0; i < M; i++) {	
			int val = in.nextInt();
			if(chk[val + 10000000] != 0) {
				res[i] = res[chk[val + 10000000]];
			}else {
				res[i] = search(0, N-1, val);
				chk[val + 10000000] = i;
			}
			System.out.print(res[i] + " ");
		}
	}
	
	public static int search(int start, int end, int val) {
		int cnt;		
		if(start <= end) {	
			int mid = (start + end) / 2;		
			if(val == arr[mid]) {
				cnt = 1;
				cnt += search(start, mid - 1, val);
				cnt += search(mid + 1, end, val);
				return cnt;
			}else {
				if(val > arr[mid]) {
					return search(mid+1, end, val);
				}else if(val < arr[mid]) {
					return search(start, mid-1, val);
				}
			}
		}
		return 0;
		
	}
}

quf9484 4년 전 0

Scanner를 BuffedReader로 바꾸니 성공했습니다

생각보다 Scanner시간이 엄청 오래걸리는가 봅니다.

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

문제

문제

출처

ICPC

10816 시간초과 도와주세요 ㅜㅜ

quf9484 4년 전 0

quf9484 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말