[99클럽 5기 코테 스터디 TIL 1일차] 암기왕 (feat. 이진탐색)

1) 문제

https://www.acmicpc.net/problem/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
5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

1
1
0
0
1

 

2) 이진 탐색의 개념

• 이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 효율적으로 찾는 알고리즘
• 핵심
  • 배열이 정렬되어 있어야 한다.
  • 찾고자 하는 값을 중간값과 비교하면서 탐색 범위를 반으로 줄인다.
  • 값을 찾으면 종료하고, 찾지 못하면 탐색 범위를 왼쪽 또는 오른쪽으로 좁힌다.

3) 이진 탐색의 동작 원리

• 중간 인덱스를 계산: mid = (low + high) / 2
• 중간값과 비교:
  • 찾는 값이 중간값과 같으면 값을 찾은 것이다.
  • 찾는 값이 중간값보다 작으면 왼쪽 절반에서 다시 탐색한다.
  • 찾는 값이 중간값보다 크면 오른쪽 절반에서 다시 탐색한다.
• 이러한 과정을 값이 발견되거나 탐색 범위가 없어질 때까지 반복한다.

이 알고리즘은 탐색 대상의 크기를 반씩 줄이므로 시간복잡도는 O(log N)

 

 

 

 

 

 

 

4) 문제 접근 방법

1. 수첩 1 데이터를 정렬하기 => 이진 탐색을 위해 데이터가 정렬되어 있어야 하기 때문
2. 수첩 2의 각 수를 수첩 1에서 이진 탐색으로 확인하기
3. 각 수를 확인한 결과(1 또는 0)를 출력하기

 

 

 

 

 

5) 내가 푼 풀이

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

public class p2776_암기왕 {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder(); //입력처리를 빠르게 하기 위해

        int T = Integer.parseInt(br.readLine()); //테스트 케이스 개수 입력
        /*
        * while(T-- > 0){}
        * for(int i=0; i<T; i++){}
        * */
        while (T-- > 0) {

            // 수첩 1 정보 입력 (note1 배열 만들어 정보 입력)
            int N = Integer.parseInt(br.readLine()); //‘수첩 1’에 적어 놓은 정수의 개수
            int[] note1 = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int i=0; i<N; i++){
                note1[i] = Integer.parseInt(st.nextToken());
            }

            // 수첩 2 정보 입력 (note2 배열 만들어 정보 입력)
            int M = Integer.parseInt(br.readLine()); //‘수첩 1’에 적어 놓은 정수의 개수
            int[] note2 = new int[M];
            st = new StringTokenizer(br.readLine());
            for(int i=0; i<M; i++){
                note2[i] = Integer.parseInt(st.nextToken());
            }

            // 수첩 1 정렬 (이진 탐색을 위해 필수!!!!!!!)
            Arrays.sort(note1);

            // 수첩 2의 각 숫자에 대해 이진 탐색 수행
            for (int num : note2) {
                if (binarySearch(note1, num)) { //‘수첩1’에 값이 있음 (탐색 완료) - 1
                    sb.append(1).append("\n");
                } else { //‘수첩1’에 값이 없음 (탐색 미완료) - 0
                    sb.append(0).append("\n");
                }
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.close();
    }

    // 이진 탐색 메서드
    public static boolean binarySearch(int[] array, int target) {
        int low = 0; //탐색할 첫번째 인덱스
        int high = array.length - 1; //탐색할 마지막 인덱스

        while (low <= high) {//(탐색할 첫번째 인덱스 <= 탐색할 마지막 인덱스)일 경우에 무한 반복
            int mid = (low + high) / 2; //탐색할 중간 인덱스

            if (array[mid] == target) { //중간값과 target값이 같으면 탐색 완료 - true
                return true;
            } else if (array[mid] < target) { //중간값보다 target값이 크면 오른쪽 절반 다시 탐색해야함 - 탐색할 첫번째값에 중간인덱스+1로 할당
                low = mid + 1;
            } else { //중간값보다 target값이 작으면 왼쪽 절반 다시 탐색해야함 - 탐색할 첫번째값에 중간인덱스-1로 할당
                high = mid - 1;
            }
        }

        return false; // 그 외는 값을 찾지 못한 것 - 탐색 미완료 - false
    }
}