[Algorithm] 99클럽 코테 스터디 1일차 TIL | 백준_암기왕(2776번)

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

---

수를 저장하고 특정 수가 있는 지 확인하는 방법에 대해 고민을 해보다가 HashSet을 사용하면 되겠다고 생각했다.

HashSet은 해시 테이블 기반 탐색으로 중복되지 않는 값에서 빠른 조회가 필요할 때 사용하곤 한다.

시간 복잡도는 평균 O(1)이다.

 

• add(E e): 값을 추가하며, 성공 여부를 반환.
• contains(Object o): 특정 값이 존재하는지 확인. (반환: true/false)
• remove(Object o): 특정 값을 제거.
• clear(): 모든 값을 제거.
• isEmpty(): 비어 있는지 확인.
• size(): 현재 저장된 요소의 개수를 반환.

 

나의 풀이

import java.util.*;
import java.io.*;
class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < T; i++){
            int N = Integer.parseInt(br.readLine());
            HashSet<Integer> set = new HashSet<>();
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < N; j++){
                set.add(Integer.parseInt(st.nextToken()));
            }
            int M = Integer.parseInt(br.readLine());
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0; j < M; j++){
                if(set.contains(Integer.parseInt(st.nextToken()))){
                    sb.append("1").append("\n");
                }else{
                    sb.append("0").append("\n");
                }
            }
        }
        System.out.println(sb.toString());
    }
}

 

처음에 StringBuilder를 사용하지 않고 매 출력마다 System.out.println을 사용했을 때 시간초과가 났었다.

시간초과를 방지하기 위해 StringBuilder를 사용해서 출력하자..!