글 읽기 - 시간 줄이는 방법이 궁금합니다

ultrawave 8년 전 0

처음에 스캐너를 이용해서 입력받았는데 시간초과가 나서 버퍼드리더로 수정했고, 똑같이 시간초과입니다

어떤 부분을 손대야 시간을 단축시킬 수 있나요?

어레이리스트를 사용한 부분을 고쳐야하나요?

감사합니다.

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

public class Main {
	public static void main(String[] args) {
		try {
			ArrayList<String> a = new ArrayList<String>();
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int t = Integer.parseInt(br.readLine());
			String str;
			StringTokenizer strToken;
			int n;
			int i, j;
			for (i = 0; i < t; i++) {
				a.clear();
				n = Integer.parseInt(br.readLine());
				str = br.readLine();
				strToken = new StringTokenizer(str, " ");
				for (j = 0; j < n; j++) {
					a.add(strToken.nextToken());
				}
				n = Integer.parseInt(br.readLine());
				str = br.readLine();
				strToken = new StringTokenizer(str, " ");
				for (j = 0; j < n; j++) {
					if (a.contains(strToken.nextToken()))
						System.out.println("1");
					else
						System.out.println("0");
				}
			}

		} catch (Exception e) {
		}
	}
}

ntopia 8년 전 0

ArrayList 의 contains 함수는 선형시간 검색을 수행하므로

테스트케이스당 시간복잡도가 O(NM) 이 되므로 제한시간 내에 답을 구할 수 없습니다.

효율적인 검색 알고리즘을 공부해보세요.

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

문제

문제

출처

ICPC

시간 줄이는 방법이 궁금합니다

ultrawave 8년 전 0

ntopia 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말