백준 2776 - 암기왕 (자바 - 이분탐색)

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

2776번: 암기왕

 

* 문제 요약

연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해보기로 한다.

동규는 연종을 따라 다니며 연종이 하루 동안 본 정수들을 모두 수첩1에 적어놓았다. 그것을 바탕으로 그가 진짜 암기왕인지 알아보기 위해 동규는 연종에게 M개의 질문을 던졌다.

질문의 내용은 X 라는 정수를 오늘 본 적이 있는가? 이다. 연종은 막힘없이 모두 대답을 했고, 동규는 연종이 봤다고 주장하는 수 들을 수첩2에 적어두었다. 집에 돌아온 동규는 답이 맞는지 확인하려 하지만, 연종을 따라다니느라 너무 힘들어서 여러분에게 도움을 요청했다. 동규를 도와주기 위해 수첩2에 적혀있는 순서대로, 각가의 수에 대하여 수첩1에 있으면 1을, 없으면 0을 출력하는 프로그램을 작성해보자.

 

* 입력

첫째 줄에 테스트케이스의 갯수 T가 들어온다. 다음 줄에는 수첩1에 적어 놓은 정수의 갯수 N (1 <= N <= 1,000,000) 이 입력으로 들어온다. 그 다음 줄에 수첩1에 적혀있는 정수들이 N개 들어온다. 그 다음 줄에는 수첩2에 적어놓은 정수의 갯수 M (1 <= M <= 1,000,000) 이 주어지고, 다음 줄에 수첩2에 적어놓은 정수들이 입력으로 M개 들어온다. 모든 정수들의 범위는 int 로 한다.

 

* 출력

수첩2에 적혀있는 M개의 숫자 순서대로 수첩1에 있으면 1을, 없으면 0을 출력한다.

 

* 예시

 

* 해결 과정

각 테스트케이스 별로 다음과 같은 로직을 수행한다.

1. 수첩1에 적혀있는 숫자들을 note 배열에 저장한 후 해당 배열을 오름차순 정렬한다.

2. 수첩2에 적혀있는 숫자들을 입력받고 나면 각 숫자들의 순서대로 다음과 같이 note 배열에 대해 이분탐색을 수행해 해당 숫자가 note 배열에 존재하는지, 그렇지 않은지 확인한다.

  - note 배열의 시작 인덱스 0 을 start, 마지막 인덱스 n-1 을 end 에 저장한 후 조건 start <= end 을 만족하는 동안 진행되는 반복문을 생성한다.

  - 변수 mid 에 (start + end) / 2 값을 저장해주고 난 다음, 만약 note 배열에서 mid 인덱스에 해당되는 값이 현재 찾고자 하는 값과 일치한다면 1을 출력하고 반복문을 종료시킨다.

  - 만약 note 배열에서 mid 인덱스에 해당되는 값이 현재 찾고자 하는 값보다 크다면 end 를 mid - 1 로 줄인다.

  - 만약 note 배열에서 mid 인덱스에 해당되는 값이 현재 찾고자 하는 값보다 작다면 start 를 mid + 1 로 늘린다.

  - 만약 찾고자 하는 값을 찾지 못한 상태로 start <= end 조건을 만족하지 못하는 상황이 발생해 반복문이 종료되었다면, note 배열에 찾고자 하는 값이 존재하지 않는다는 뜻이므로 0 을 출력해준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int tc = Integer.parseInt(br.readLine());
        for (int i = 0; i < tc; i++) {
            int n = Integer.parseInt(br.readLine());
            String[] input = br.readLine().split(" ");

            int[] note = new int[n];
            for (int j = 0; j < n; j++) {
                note[j] = Integer.parseInt(input[j]);
            }

            Arrays.sort(note);

            int m = Integer.parseInt(br.readLine());
            input = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                int findNumber = Integer.parseInt(input[j]);

                int start = 0;
                int end = n - 1;
                boolean find = false;
                while (start <= end) {
                    int mid = (start + end) / 2;

                    if (note[mid] == findNumber) {
                        bw.write(1 + "\n");
                        find = true;
                        break;
                    } else if (note[mid] > findNumber) {
                        end = mid - 1;
                    } else {
                        start = mid + 1;
                    }
                }

                if (!find) {
                    bw.write(0 + "\n");
                }
            }
        }

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

 

오름차순으로 정렬된 배열에 대해 일정 크기의 범위를 잡고, 해당 범위 내부의 중간값의 상태가 찾고자 하는 값이 아니라면 조건에 맞춰 범위를 줄이는 방식으로 특정 숫자를 찾았으므로 이분탐색 문제에 해당된다.