[Set & List] 성능 차이

코딩 테스트를 준비하며 백준을 풀고 있었습니다.

 

https://www.acmicpc.net/problem/1920

1920번: 수 찾기

바로 이 문제인데요?

 

생각보다 간단한 문제이고 쉽게 풀었는데, 계속 시간 초과가 났었습니다..

원인이 무엇인고, 하고 봤습니다.

 

첫 번째 문제

입력한 숫자 만큼 정수를 받아서 자료구조에 저장하고 contains로 비교할 생각이었습니다.

당연히 정수이므로 Integer로 제네릭을 선언했는데, 이게 변환과정에서 시간을 좀 잡아먹을 수 있다는 생각을 못했네요 ㅎㅎ

StringTokenizer st;

List<Integer> numbers = new ArrayList<>();
// String을 입력 값으로 넣기 때문에,

int N = Integer.parseInt(br.readLine());

st = new StringTokenizer(br.readLine());

for (int i = 0; i < N; i++) {
    String token = st.nextToken();
    numbers.add(Integer.parseInt(token)); // 여기서 한번 Wrapping을 해줘야 하는데, 시간이 걸림.
}

 

두 번째 문제

단순히 List 자료구조를 이용해서 contains 비교를 할 생각이었는데, 이게 화근이었습니다.

List와 Set의 차이는 순서가 보장되냐, 중복 허용이냐 차이인데 결정적으로 순서가 중요한 것이 아닌 중복을 허용하지 않는 게 문제의 입력입니다.

또 Collection의 contains()는 List Set 의 시간 복잡도가 O(n), O(1) 이므로 데이터가 많아질 수록 엄청난 속도 차이가 나는 것을 알게 되었습니다.

이 점을 잘 숙지하고 다음 문제들을 마주해봐야겠다는 생각을 했습니다.

List<String> numbers2 = new ArrayList<>(); // 이것을 
Set<String> numbers1 = new HashSet<>(); // 이것으로