boj1920 수 찾기_java

링크

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

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -2^31보다 크거나 같고 2^31보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

나의 풀이

• 이문제는 BigInteger를 사용해야하는 문제다.

• 이분탐색으로 풀었다.

• 먼저 N크기의 배열을 정렬하고, M크기의 값을 하나씩 받으면서 문제를 해결하였다. left와 right값을 갱신해가면서 N크기의 배열안에 값고 같은지 여부를 찾았다.
  left는 0 , right는 N-1을 초기값으로 하였다. mid를 구하고, 이 mid위치에 있는 배열값보다 크면 (now>arr.get(mid)) right값을 갱신해주었고, mid위치에 있는 배열값보다 작으면(now<arr.get(mid)) left값을 갱신해주었다.
  이때, mid위치에 있는 배열값과 내가 찾고자하는 값이 같으면, flag를 true로 표시하고, 1이라고 출력한뒤에 배열을 break한다.

• 핵심 코드

  for (int i = 0; i < M; i++) {
              BigInteger now = new BigInteger(st.nextToken());
              int right = N-1;
              int left = 0;
              boolean flag = false;
              while(left<=right){
                  int mid = (right+left)/2;
                  if(now.compareTo(arr.get(mid))==0){
                      sb.append(1).append("\n");
                      flag = true;
                      break;
                  }else if(now.compareTo(arr.get(mid))==-1){
                      right = mid-1;
                  }else if(now.compareTo(arr.get(mid))==1){
                      left = mid+1;
                  }
              }
              if(!flag) sb.append(0).append("\n");
          }

• 전체 코드_이전코드 개선

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.*;
  import java.math.*;
  import java.lang.*;
  
  public class boj1920 {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = null;
          StringBuilder sb = new StringBuilder();
          List<BigInteger> arr = new ArrayList<>();
          int N = Integer.parseInt(br.readLine());
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < N; i++) {
              arr.add(new BigInteger(st.nextToken()));
          }
          Collections.sort(arr);
  
          int M = Integer.parseInt(br.readLine());
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < M; i++) {
              BigInteger now = new BigInteger(st.nextToken());
              int right = N-1;
              int left = 0;
              boolean flag = false;
              while(left<=right){
                  int mid = (right+left)/2;
                  if(now.compareTo(arr.get(mid))==0){
                      sb.append(1).append("\n");
                      flag = true;
                      break;
                  }else if(now.compareTo(arr.get(mid))==-1){
                      right = mid-1;
                  }else if(now.compareTo(arr.get(mid))==1){
                      left = mid+1;
                  }
              }
              if(!flag) sb.append(0).append("\n");
          }
  
          System.out.println(sb.toString());
      }
  }

• 전체 코드

  package Baekjoon.java.silver;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.*;
  import java.math.*;
  import java.lang.*;
  
  public class boj1920 {
      public static void main(String[] args) throws Exception{
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = null;
          StringBuilder sb = new StringBuilder();
          List<BigInteger> arr = new ArrayList<>();
          int N = Integer.parseInt(br.readLine());
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < N; i++) {
              arr.add(new BigInteger(st.nextToken()));
          }
          Collections.sort(arr);
  
          List<BigInteger> my = new ArrayList<>();
          int M = Integer.parseInt(br.readLine());
          st = new StringTokenizer(br.readLine());
          for (int i = 0; i < M; i++) {
              my.add(new BigInteger(st.nextToken()));
          }
          for (int i = 0; i < M; i++) {
              BigInteger now = my.get(i);
              int right = N-1;
              int left = 0;
              boolean flag = false;
              while(left<=right){
                  int mid = (right+left)/2;
                  if(now.compareTo(arr.get(mid))==0){
                      sb.append(1).append("\n");
                      flag = true;
                      break;
                  }else if(now.compareTo(arr.get(mid))==-1){
                      right = mid-1;
                  }else if(now.compareTo(arr.get(mid))==1){
                      left = mid+1;
                  }
              }
              if(!flag) sb.append(0).append("\n");
          }
  
          System.out.println(sb.toString());
      }
  }

결과