이분 탐색(1920, 10816)

[수 찾기 _ 1920]

 

import java.util.Arrays;
import java.util.Scanner;

public class Problem_1920 {
    static int[] arr;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        arr = new int[N];
        for(int i=0; i<N; ++i){
            arr[i] = scanner.nextInt();
        }
        Arrays.sort(arr);

        int M = scanner.nextInt();
        while (M > 0){
            int x = scanner.nextInt();
            if(searchNum(x)){
                System.out.println(1);
            }
            else System.out.println(0);

            M--;
        }
    }

    private static boolean searchNum(int x) {
        int front = 0;
        int rear = arr.length-1;
        while (front <= rear){
            int mid = (front + rear) / 2;

            if(arr[mid] == x) return true;
            else if(x < arr[mid]) rear = mid-1;
            else if(x > arr[mid]) front = mid+1;
        }

        return false;
    }
}

 

 

[숫자 카드 2 _ 10816]

 

 

 

* 알고리즘

• 이분 탐색

 

* 로직

• 주어진 카드에 대해 배열 인덱스로 카드 수를 관리한다
• 음수를 커버하기 위해 값 + 10000000을 해준다
• 찾고자 하는 카드의 인덱스로 접근하면 원하는 카드의 수를 얻을 수 있다

 

import java.util.Scanner;

public class Problem_10816 {
    static int[] counts = new int[20000001];

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        for(int i=0; i<N; ++i){
            int tmp = scanner.nextInt();
            counts[tmp + 10000000]++;
        }

        int M = scanner.nextInt();
        while (M > 0){
            int x = scanner.nextInt();
            System.out.print(counts[x + 10000000] + " ");

            M--;
        }
    }
}