[백준 자바] 1920번(수 찾기) - Set, 이진 탐색, Arrays.binarySearch()

실버 4

문제

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을 출력한다.

 

---

 

728x90

1. Set 집합

N개의 정수 A[1], A[2], …, A[N]을 Set에 저장하여 Set.contains를 이용해 X가 Set에 있는지 확인한다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    Set<Integer> A = new HashSet<>();

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < N; i++) {
      A.add(Integer.parseInt(st.nextToken()));
    }

    int M = Integer.parseInt(br.readLine());

    StringBuilder sb = new StringBuilder();

    st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < M; i++) {
      sb.append(A.contains(Integer.parseInt(st.nextToken())) ? '1' : '0').append('\n');
    }

    bw.write(sb.toString());

    bw.flush();
    br.close();
    bw.close();
  }
}

 

2. 이진 탐색

이진 탐색을 하기 위해 배열 A를 오름차순으로 정렬한다.

검색값이 배열A의 중앙값보다 크면 검색 범위를 중앙값의 뒤쪽으로 좁히고, 중앙값보다 작으면 검색 범위를 중앙값의 앞쪽으로 좁힌다. 중앙값이 검색값과 일치할 때까지 반복한다.

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

public class Main1920 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    int[] A = new int[N];

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(A);

    int M = Integer.parseInt(br.readLine());

    StringBuilder sb = new StringBuilder();

    st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < M; i++) {
      int key = Integer.parseInt(st.nextToken());
      int pl = 0;
      int pr = N - 1;
      boolean found = false;

      do {
        int pc = (pl + pr) / 2;
        if (A[pc] == key) {
          sb.append('1').append('\n');
          found = true;
          break;
        } else if (A[pc] < key)
          pl = pc + 1;
        else
          pr = pc - 1;
      } while (pl <= pr);

      if (!found)
        sb.append('0').append('\n');
    }

    bw.write(sb.toString());

    bw.flush();
    br.close();
    bw.close();
  }
}

• pl: 검색 범위의 첫 인덱스
• pr: 검색 범위의 마지막 인덱스
• pc: 중앙 요소의 인덱스
• 검색값 key가 중앙값보다 큰 경우 pl을 pc + 1로 하여 검색 범위를 뒤 절반으로 좁힘
• 검색값 key가 중앙값보다 작은 경우 pr을 pc - 1로 하여 검색 범위를 앞 절반으로 좁힘
• key값을 찾으면 1 리턴
• pl = pr이 될 때까지 key를 찾지 못한 경우(found = false) 0 리턴

3. Arrays.binarySearch

배열에서 이진 탐색을 하는 메서드(java.util.Arrays)

검색에 성공한 경우 key와 일치하는 요소의 인덱스를, 검색에 실패한 경우 배열에 key가 있어야 할 위치(삽입 포인트)를 반환한다. 삽입 포인트를 x라 할 때 반환값은 -x-1이다.

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

public class Main1920 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int N = Integer.parseInt(br.readLine());
    int[] A = new int[N];

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < N; i++) {
      A[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(A);

    int M = Integer.parseInt(br.readLine());

    StringBuilder sb = new StringBuilder();

    st = new StringTokenizer(br.readLine(), " ");
    for (int i = 0; i < M; i++) {
      int key = Integer.parseInt(st.nextToken());

      sb.append(Arrays.binarySearch(A, key) >= 0 ? '1' : '0').append('\n');
    }

    bw.write(sb.toString());

    bw.flush();
    br.close();
    bw.close();
  }
}