[Baekjoon] 1920번 : 수 찾기

1. 문제

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안에 존재하는지 알아내면 된다.
모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

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

// 예제 입력 1
5
4 1 5 2 3
5
1 3 7 9 5

// 예제 출력 1
1
1
0
0
1

2. 핵심 아이디어

• 특정 정수의 등장 여부만을 간단히 체크
• dictionary 자료형을 해시처럼 사용할 수 있음
• set 자료형을 이용해 더욱 간단히 풀 수 있음

3. Python 문제풀이

# 풀이 1
import sys

n = int(sys.stdin.readline())
n_number = set(map(int, sys.stdin.readline().split()))

m = int(sys.stdin.readline())
m_number = list(map(int, sys.stdin.readline().split()))

for i in m_number :
  if i not in n_number :
    print('0')
  else :
    print('1')

# 풀이 2
import sys
input = sys.stdin.readline

n, nNumber = int(input()), {i: 1 for i in map(int, input().split())}
m, mNumber = int(input()), list(map(int, input().split()))

for i in mNumber :
  print(nNumber.get(i, 0))

4. Java 문제풀이

import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] n_number = new int[n];

    for (int i = 0; i < n; i++) {
      n_number[i] = sc.nextInt();
    }

    Arrays.sort(n_number);

    int m = sc.nextInt();
    int[] m_number = new int[m];

    for (int i = 0; i < m; i++) {
      m_number[i] = sc.nextInt();
    }

    for (int i = 0; i < m; i++) {
      System.out.println(binarySearch(n_number, m_number[i]));
    }
  }

  public static int binarySearch(int[] arr, int target) {
    int left = 0;
    int mid = 0;
    int right = arr.length - 1;

    while (left <= right) {
      mid = (left + right) / 2;
      if (arr[mid] == target) {
        return 1;
      }
      else if (arr[mid] > target) {
        right = mid - 1;
      }
      else if (arr[mid] < target) {
        left = mid + 1;
      }
    }
    return 0;
  }
}