[BOJ] 2776 암기왕 - JAVA

1. 문제

2776번: 암기왕

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, 연종이 하루 동안 본 정수들을 모두 ‘수첩1’에 적어 놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해, 동규는 연종에게 M개의 질문을 던졌다. 질문의 내용은 “X라는 정수를 오늘 본 적이 있는가?” 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 ‘수첩2’에 적어 두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 ‘수첩2’에 적혀있는 순서대로, 각각의 수에 대하여, ‘수첩1’에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

---

2. 풀이

Main

인풋을 받고 배열을 정렬한다.

M개의 인풋을 하나씩 받으면서 binarySearch 메서드가 true면 sb에 1, false면 0을 더한다.

static int[] number;
static int N;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int T = Integer.parseInt(in.readLine());
   StringBuilder sb = new StringBuilder();

   for(int tc=0;tc<T;tc++){
      N = Integer.parseInt(in.readLine());
      number = new int[N];
      StringTokenizer st = new StringTokenizer(in.readLine());
      for(int i=0;i<N;i++) number[i] = Integer.parseInt(st.nextToken());
      Arrays.sort(number);

      int M = Integer.parseInt(in.readLine());
      st = new StringTokenizer(in.readLine());
      for(int i=0;i<M;i++){
         if(binarySearch(Integer.parseInt(st.nextToken()))) sb.append("1\n");
         else sb.append("0\n");
      }
   }
   System.out.print(sb);
}

 

이분탐색

기본적인 이분탐색 코드지만, Arrays.binarySearch에서 새로 들어가야 하는 위치를 반환하는 것과 다르게 배열 내 존재 여부를 boolean으로 반환한다.

number[m]이 x보다 크거나 같으면 h를, 작으면 l을 변경한다.

마지막에 l이 배열 범위 내 인덱스인지 확인하고 number[l]==x여부를 리턴한다.

public static boolean binarySearch(int x){
   int l = 0, h = N-1;
   int m;
   while(l<=h && h < N){
      m = (l+h)/2;

      if(number[m] >= x) h = m-1;
      else l = m+1;
   }

   return l<N && number[l]==x;
}

 

전체 코드

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

public class BOJ_2776_암기왕 {
   static int[] number;
   static int N;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(in.readLine());
      StringBuilder sb = new StringBuilder();

      for(int tc=0;tc<T;tc++){
         N = Integer.parseInt(in.readLine());
         number = new int[N];
         StringTokenizer st = new StringTokenizer(in.readLine());
         for(int i=0;i<N;i++) number[i] = Integer.parseInt(st.nextToken());
         Arrays.sort(number);

         int M = Integer.parseInt(in.readLine());
         st = new StringTokenizer(in.readLine());
         for(int i=0;i<M;i++){
            if(binarySearch(Integer.parseInt(st.nextToken()))) sb.append("1\n");
            else sb.append("0\n");
         }
      }
      System.out.print(sb);
   }
   
   public static boolean binarySearch(int x){
      int l = 0, h = N-1;
      int m;
      while(l<=h && h < N){
         m = (l+h)/2;

         if(number[m] >= x) h = m-1;
         else l = m+1;
      }

      return l<N && number[l]==x;
   }
}

---

3. 결과

Arrays.binarySearch를 사용해서 0보다 큰지, 작은지로 판단해도 됐지만 이분탐색 푼 지 너무 오래 된 것 같아서 직접 구현해보았다.