[TIL] ArrayList vs HashSet

기록을 남기지 않으면 내 기억 속에서 다 사라지는걸 너무나도 느껴서!!!.. 틈틈히 공부한 것 중에서 알게된걸 기록으로 남겨보겠다.

최근에 파이썬에서 자바로 코테 언어를 바꿔서 공부하고 있는데 모르는 메소드랑 개념들이 꽤 있어서 정리를 해야할거같다

백준 22233 문제를 푸는데 시간초과가 떴다.

🙅🏻‍♀️ 시간초과 코드

package 구현;

import java.util.*;
import java.io.*;

public class boj22233 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 메모장에 적은 키워드 수
        int M = Integer.parseInt(st.nextToken()); // 블로그에 쓴 글

        List<String> keywords = new ArrayList<>(); // 메모장에 적은 키워드
        List<String> relateds = new ArrayList<>(); // 관련된 키워드

        for (int i = 0; i < N; i++) {
            keywords.add(br.readLine());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), ",");
            while (st.hasMoreTokens()) {
                String relate = st.nextToken();
                relateds.add(relate);
            }

            List<String> toRemove = new ArrayList<>();
            for (String keyword : keywords) {
                if (relateds.contains(keyword)) {
                    toRemove.add(keyword);
                }
            }

            keywords.removeAll(toRemove);
            System.out.println(keywords.size());
        }
    }

}

🙆🏻‍♀️ 정답 코드

package 구현;

import java.util.*;
import java.io.*;

public class boj22233 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 메모장에 적은 키워드 수
        int M = Integer.parseInt(st.nextToken()); // 블로그에 쓴 글

        Set<String> keywords = new HashSet<>(); // 메모장에 적은 키워드

        for (int i = 0; i < N; i++) {
            keywords.add(br.readLine());
        }

        for (int i = 0; i < M; i++) {
            Set<String> relateds = new HashSet<>(); // 관련된 키워드

            // 쉼표로 구분 받아서 저장
            st = new StringTokenizer(br.readLine(), ",");

            while (st.hasMoreTokens()) {
                String relate = st.nextToken();
                relateds.add(relate);
            }

            keywords.removeAll(relateds);

            System.out.println(keywords.size());
        }
    }

}

Why?

왜 시간 초과가 떴을까 보니 ArrayList는 선형 탐색으로 검색 속도가 O(N)이고 HashSet은 O(1)로 월등히 빨랐다. 이 문제의 경우 입력 수가 2×10^5 까지로 컸기 때문에 시간 초과가 난 것 같다.

만약 키워드가 100,000개 있는데 관련 키워드를 3개 삭제한다고 치자.
그럼 ArrayList는 O(N)의 시간 복잡도로 3x100,000 = 30만번이 걸리고 HashSet은 O(1)로 3번으로 찾을 수 있다.

추가로, Hashset끼리의 연산은 O(1)으로 매우 빠르다. 이 경우 hashSet 끼리 저장 여부를 비교해서 삭제하는 것이기 때문에 시간 측면에서 매우 유리하다.

ArrayList vs HashSet

항목	ArrayList	HashSet
저장 구조	순차적인 리스트 구조	중복 없는 집합 구조
순서	삽입 순서 유지	순서 유지 안됨 (필요하면 LinkedHashSet)
중복 허용 여부	허용	불가
검색 속도	끝에 추가하는 경우: O(N) / 중간이나 앞에 삽입하는 경우: O(N)	O(1)
삽입 속도	O(1)	O(1)
삭제 속도	O(1)	O(1)
정렬	Collections.sort() 로 정렬 가능	자체 정렬 기능 x (정렬하려면 List로 변경해야함)

그럼 언제 어떤 걸 써야할까?

• 중복이 허용되고 순서가 중요하다면 ArrayList
• 중복 제거가 필요하고 순서가 상관 없다면 HashSet
• 정렬이 필요하거나 인덱스로 접근해야한다면 ArrayList
  그래서 만약에 HashSet으로 인덱스 접근해야하면 List로 변경해야함

List<String> list = new ArrayList<>(set);
System.out.println(list.get(0));

• 빠른 검색과 삭제가 필요할 때 (입력 값이 클 때) HashSet