[DAY37] 99클럽 코딩테스트 JAVA 백준 암기왕 2776번 (시간초과 해결)

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

---

🌘문제 이해하기 

•  연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 
• 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 
• 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 
• 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력

---

🌗문제 자세히보기

 이분탐색을 활용하거나 set을 활용하여 문제를 해결 할 수 있다. 

문제 형태가 간단하여 이분탐색을 활용하지 않아도 set을 활용하는 것이 더 효율적인 거 같아 set 방식을 활용해보겠다. 

 

1. 연종이가 본 정수들을 수첩1에 적어 놓는다. 

•  수첩1을 hashset 형태로 생성한다.
• 정수들을 hashset 에 add 

🚨 list 형태로 생성해도 되지만, hashset은 중복을 허용하지 않아 시간초과를 막을 수 있다. 

 

 

2. 동규는 연종이가 봤다고 주장하는 정수들을 수첩2에 적어 두었다.

• 수첩2는 배열 형태로 생성한다.
• 정수들을 int[]  에 추가

3.  수첩2를 기준으로 정수들이 수첩1에 포함되어 있다면 "1" , 포함되어 있지 않다면 "0" 을 출력 하지 않고!

StringBuilder 형식으로 append 해준다.

🚨 흔히 사용하는 System.out.println() 형식으로 매 순간 출력하면 시간초과 가 발생한다.
  정수의 개수가 최대 1,000,000 개인데 최대치 만큼 println 을 하면 시간초과가 발생한다. 

 

이를 방지하기위해서 StringBuilder 형식으로 한 테스트 케이스동안에는 append 하여 한번에 출력을 하도록 한다. 

---

🌕 최종코드

 

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));     

          //테스트 케이스 
          int t = Integer.parseInt(br.readLine());  
          StringBuilder sb = new StringBuilder();
          
          for(int i=0;i<t;i++)
          {
               //수첩1에 정수의 개수
               int num1 = Integer.parseInt(br.readLine());

               //수첩1에 정수들
               HashSet<Integer> note1 = new HashSet<>();

               StringTokenizer st = new StringTokenizer(br.readLine());
               for(int j=0;j<num1;j++)
               {
                    note1.add(Integer.parseInt(st.nextToken()));
               }

               //수첩2에 정수의 개수
               int num2 = Integer.parseInt(br.readLine());

               //수첩2에 정수들
               int[] note2 = new int[num2];

               st = new StringTokenizer(br.readLine());
               for(int j=0;j<num2;j++)
               {
                    note2[j] = Integer.parseInt(st.nextToken());
               }

               //암기 확인
               for(int x=0;x<num2;x++)
               {
                    if(note1.contains(note2[x]))
                         sb.append("1\n");
                         //System.out.println("1"); //note1 에 있으면 1
                    else 
                         sb.append("0\n");
                         //System.out.println("0"); //note1 에 없으면 0
               }
          }

          System.out.println(sb);
     }
}