[백준/JAVA] 해시를 사용한 집합과 맵 10815 숫자 카드

나의 답) 904ms

import java.io.*;
import java.util.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
        HashSet<Integer> set = new HashSet<>();
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            set.add(Integer.parseInt(st.nextToken()));
        }
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int comp = Integer.parseInt(st.nextToken());
            sb.append(set.contains(comp) ? "1 " : "0 ");
        }
        
        System.out.print(sb.toString().trim());
    }
}

 

 

시간 복잡도

1. HashSet에 데이터 삽입

• set.add()는 평균적으로 O(1)의 시간 복잡도를 가진다.
• 따라서 n개의 데이터를 삽입하는 데 걸리는 총 시간은 O(n)이다.

2. HashSet을 이용한 탐색

• set.contains()는 평균적으로 O(1)의 시간 복잡도를 가진다.
• m개의 쿼리에 대해 탐색하므로 총 시간은 O(m)이다.

3. StringBuilder의 append 연산

• 각 append는 상수 시간 O(1)에 수행되므로 총 O(m)이다.

4. StringBuilder의 trim()

• 결과 문자열의 길이를 k라고 하면, trim()의 시간 복잡도는 O(k)이다.
• 문제의 출력 형식에서 k는 2m - 1(각 결과 + 공백)이며, 이 경우 O(m)로 간주할 숭 있다.

=> 총 시간 복잡도: O(n + m)