백준 22233 : 가희와 키워드 [JAVA]

[문제 링크]

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

[난이도]

- Silver 2

 

[알고리즘]

- LinkedHashSet

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        // 🔹 HashSet 대신 LinkedHashSet 사용 (입력 순서 유지 가능)
        Set<String> keywords = new LinkedHashSet<>();
        for (int i = 0; i < N; i++) {
            keywords.add(br.readLine());
        }

        for (int i = 0; i < M; i++) {
            String[] words = br.readLine().split(",");
            for (String word : words) {
                keywords.remove(word); // ✅ 평균 O(1)로 최적화됨
            }
            bw.write(keywords.size() + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

[풀이]

처음엔 List로 풀었지만 List.remove() 는 for문으로 전체탐색을 한번진행하며 삭제하는 메서드이므로 최악의 경우 O(N*M)가 걸린다. LinkedHashSet은 O(1)이 걸린다.

 

그렇다면 언제 LinkedHashSet을 쓰면 좋을까?

1. 중복을 허용하지 않아야 할때 -> List는 중복 허용, LinkedHashSet은 중복을 제거함.

2. 입력된 순서를 유지해야 할 때 -> HashSet은 순서를 보장하지 않지만, LinkedHashSet은 순서를 유지.

3. 탐색보다는 삭제 연산이 많을 때 -> ArrayList는 삭제 시 O(N)인데, LinkedHashSet은 O(1)에 가깝다.

 

하지만 LinkedHashSet을 쓰면 안되는 경우도 있다.

1. 빠른 인덱스 접근이 필요할 때

• ArrayList.get(index)는 O(1)로 빠르지만 LinkedHashSet은 인덱스로 직접 접근할 수 없다.

2. 메모리를 아껴야 할 때

3. 데이터가 중복될 가능성이 없거나, 순서가 중요하지 않을 때

 

결론 : 언제 LinkedHashSet을 써야 할까?

• 중복을 방지해야 하고, 순서를 유지해야하며, 삭제 연산이 많을 때 -> LinkedHashSet
• 탐색이나 삽입 속도가 중요하고, 중복을 허용해도 된다면 -> ArrayList
• 인덱스로 직접 접근해야 한다면 -> ArrayList