글 읽기 - 시간초과 에러 도와주세요!

testoog 4년 전 0

시간초과 에러가 납니다..

Arrays.asList().contains()를 써서 그런가 해서 33번째 줄을

int mInteger = Integer.parseInt(stringTokenizer.nextToken());

for(int n : nArray){

if(n==mInteger){

bufferedWriter.write("1\n");

rCount++; break;

}

if(rCount-1!=m){

bufferedWriter.write("0\n");

rCount++;

}

이런 식으로 바꿔봤는데 그래도 시간초과 에러가 나네요.. 어디가 문제인걸까요ㅠㅠ

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) {
		InputStreamReader inputStreamReader = new InputStreamReader(System.in);
		BufferedReader bufferedReader = new BufferedReader(inputStreamReader);
		
		OutputStreamWriter outputStreamWriter = new OutputStreamWriter(System.out);
		BufferedWriter bufferedWriter = new BufferedWriter(outputStreamWriter);
		
		try{
			int nCount = Integer.parseInt(bufferedReader.readLine());
			StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
			
			Integer[] nArray = new Integer[nCount];
			for(int n=0; n<nCount; n++){
				nArray[n] = Integer.parseInt(stringTokenizer.nextToken());
			}
			
			
			int mCount = Integer.parseInt(bufferedReader.readLine());
			stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
			
			int rCount = 0;
			for(int m=0; m<mCount; m++){
				bufferedWriter.write((Arrays.asList(nArray).contains(Integer.parseInt(stringTokenizer.nextToken()))?"1":"0")+"\n");
			}
			
			bufferedWriter.flush();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} finally {
			try {
				bufferedReader.close();
				bufferedWriter.close();
			} catch (IOException e) {
				// TODO Auto-generated catch block
				e.printStackTrace();
			}
		}
	}
}

djm03178 4년 전 0

둘은 근본적으로 차이가 없습니다. 선형 시간에 찾지 않게 해야 합니다.

qahira 4년 전 0

두 코드 모두 단순히 선형탐색을 하고있습니다만, 본 문제는

단순히 선형탐색을 하는 문제가 아니기 때문에 안풀리는 것입니다.

데이터 N개가 있으면, N을 모두 찾아봐야하기 때문에 테스트케이스처럼 작은 경우엔 풀렸을지 모르겠지만,

최악의 경우, 즉 N과 M이 각각 100,000 인 경우엔 M*N = 10,000,000,000 이므로 시간내에 절대 찾을 수 없습니다.

이진탐색을 참고해 보세요.

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

문제

문제

출처

ICPC

시간초과 에러 도와주세요!

testoog 4년 전 0

djm03178 4년 전 0

qahira 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말