글 읽기 - 시간초과가 발생하였는데 어느 부분을 수정해야될지 알려주세요

khseob0715 7년 전 0

입력 받을만큼 받아서 있나 없나만 확인하고 개수 증가한게 전부인데

시간초과 걸렸습니다.

어느 부분이 시간을 많이 잡아먹는지 좀 알려주세요

import java.util.Scanner;
import java.util.Vector;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		Vector<Integer> av = new Vector<Integer>();
		for(int i = 0 ; i < a; i++)
			av.add(in.nextInt());
		int ct = 0;
		for(int i = 0 ; i < b; i++){
			if(av.contains(in.nextInt()))
				ct++;
		}

		System.out.println((b-ct)+(a-ct));
	}
}

jseo 7년 전 2

1) 자바의 Scanner은 매우 느립니다. BufferedReader을 쓰는걸 추천합니다.

2) Vector의 contains 함수는 시간 복잡도가 O(n) 입니다. 그래서 총 시간 복잡도는 최악의 경우 O(|A||B|)가 나올수 있습니다 (A와 B가 서로소 집합일때)

이 문제는 적절한 해쉬테이블/트리 자료구조를 이용해서 O(|A| + |B|)나 O(|A| log |A| + |B| log |A|) 로 풀 수 있습니다.

p.s. 사실 문제풀이용 목적으로는 크게 상관 없지만 Vector 클래스 보다는 ArrayList 쓰는걸 권장합니다. 레거시 코드 때문에 자바 api에 아직도 있지만, Vector 클래스에 문제가 좀 있습니다.

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

문제

문제

출처

ICPC

시간초과가 발생하였는데 어느 부분을 수정해야될지 알려주세요

khseob0715 7년 전 0

jseo 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말