[Java]BOJ 2776 : 암기왕

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

🚩문제

🔒문제해결(시간초과)

비교 해야할 정수의 개수 N이 1 ≤ N ≤ 1,000,000범위이므로, 매번 System.out.println()으로 출력하면 시간 초과가 발생할 수 있습니다. StringBuilder에 모아두었다가 마지막에 한번만 System.out.println()로 출력하는것을 선택

 

1. 테스트 케이스 개수만큼 for문을 진행하고 그 안에서, N과 M값을 입력

2. 숫자 리스트에  입력받은 N과 M 의 정수를 저장하고 for문을 돌면서 일치하는 것이 존재하면 1,없으면 0을 저장 하여 출력

두 리스트간 모든 요소 비교로 O(N×M)

🔓문제해결(HashSet)

HashSet : O(1)의 시간 복잡도검색,삽입,삭제 작업 수행

 

수첩2에 적혀있는 순서대로 비교해야하므로

수첩1의 값만 HashSet에 저장하여 향상된 for문을 이용하여 해당값이 수첩1에 존재하는지 contains로 비교하여

존재하면 1, 없으면 0 StringBuilder에 저장.(한 줄에 하나씩이므로 개행문자도 추가)

 

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

/*
* 입력 *
* 테스트 케이스 개수 T
* 수첩1에 적어 놓은 정수 개수 N
* 정수N개
* 수첩2에 적어 놓은 정수 개수 M
* 정수 M개
*
* 출력 *
* 한줄에 한개씩 수첩2에 적혀있는 M개의 숫자 순서대로, 수첩1에 있으면 1,없으면 0 출력
*
*/
public class Main {
    public static void main(String[] args) throws IOException {
        // 입력을 효율적으로 처리하기 위해 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder(); // 출력값을 모아놓기 위한 StringBuilder 사용

        // 테스트 케이스 개수 입력
        Integer T = Integer.parseInt(br.readLine());

        // 테스트 케이스 개수만큼 반복
        for (int i = 0; i < T; i++) {
            // 수첩1에 적힌 정수 개수 N 입력
            int N = Integer.parseInt(br.readLine());

            // 수첩1의 정수를 저장할 HashSet 생성
            HashSet<Integer> set1 = new HashSet<>();
            String[] str1 = br.readLine().split(" "); // 수첩1의 정수들 입력받아 split

            // 수첩1의 정수를 HashSet에 추가
            for (String n : str1) {
                set1.add(Integer.parseInt(n));
            }

            // 수첩2에 적힌 정수 개수 M 입력
            int M = Integer.parseInt(br.readLine());
            String[] str2 = br.readLine().split(" "); // 수첩2의 정수들 입력받아 split

            // 수첩2의 정수들을 수첩1의 HashSet과 비교
            for (String m : str2) {
                if (set1.contains(Integer.parseInt(m))) {
                    sb.append("1").append("\n"); // 수첩1에 있으면 1 추가
                } else {
                    sb.append("0").append("\n"); // 없으면 0 추가
                }
            }
        }

        // 한 번만 출력
        System.out.println(sb);
    }
}