99클럽 코테 스터디 1일차 TIL + HashSet

[BOJ 2776: 암기왕] 문제 바로가기

❓문제 설명

❗️문제 풀이

첫째 줄엔 테스트 케이스의 개수,

두 번째 줄과 네 번째 줄은 각각 수첩 1에 적혀있는 정수 N, 수첩 2에 적어놓은 정수 M이 들어온다.

세 번째 줄과 다섯번째 줄은 각각 N개의 정수, M개의 정수가 공백을 기준으로 입력된다.

 

처음 문제를 풀 때, 몇 가지 실수를 해 시간초과가 발생했다.

while (T > 0){
            T--;
            int N = Integer.parseInt(br.readLine());
            int[] nums_1 = new int[N];
            StringTokenizer st_1 = new StringTokenizer(br.readLine());
            for(int i = 0; i < N; i++){
                nums_1[i] = Integer.parseInt(st_1.nextToken());
            }

            int M = Integer.parseInt(br.readLine());
            int[] nums_2 = new int[M];
            StringTokenizer st_2 = new StringTokenizer(br.readLine());
            for(int i = 0; i < M; i++){
                nums_2[i] = Integer.parseInt(st_2.nextToken());
            }
            
            for(int i = 0; i < M; i++){
                int current = nums_2[i];
                if(!IntStream.of(nums_1).anyMatch(x -> x==current)){
                    System.out.println(0);
                }
                else {
                    System.out.println(1);
                }
            }

수첩1과 수첩2를 모두 array 형태로 입력받아

수첩2 array를 돌며 각 index마다 수첩1 array에 존재하는지 확인했다.

이런 경우, 시간 복잡도가 O(N*M)이 되므로 N과 M이 매우 커질 경우 시간 초과가 발생한다.

📌전체 코드

import java.io.*;
import java.util.*;
public class jan_13th {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        while (T > 0){
            T--;
            int N = Integer.parseInt(br.readLine());
            HashSet<Integer> set = new HashSet<>(); // 배열을 HashSet으로 저장
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                set.add(Integer.parseInt(st.nextToken()));
            }

            int M = Integer.parseInt(br.readLine());
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            StringBuilder sb = new StringBuilder(); // 출력 최적화를 위해 사용
        
            for (int i = 0; i < M; i++) {
            int num = Integer.parseInt(st2.nextToken());
            if (set.contains(num)) { // HashSet에 존재 여부 확인
                sb.append("1\n");
            } else {
                sb.append("0\n");
            }
        }
        
        // 결과 출력
        System.out.print(sb);
        }
    }
}

이렇게 수첩1 array를 set으로 변경 후,

수첩2의 숫자를 입력받는대로 set에 존재하는지 확인하면 시간초과가 발생하지 않는다.