khseob0715   4년 전

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

시간초과 걸렸습니다.

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

jseo   4년 전

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 클래스에 문제가 좀 있습니다. 

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