백준 10815번 숫자 카드

문제

나의 풀이

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

public class Main {
    public static boolean binary_search(int[] a, int num) {
        int n = a.length;
        int left = 0;
        int right = n - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(a[mid] == num) {
                return true;
            } else if(a[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String line[] = br.readLine().split(" ");
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(a);
        int m = Integer.parseInt(br.readLine());
        line = br.readLine().split(" ");
        StringBuilder answer = new StringBuilder();
        for(int i = 0; i < m; i++) {
            int num = Integer.parseInt(line[i]);
            boolean result = binary_search(a, num);
            if(result) {
                answer.append("1 ");
            } else {
                answer.append("0 ");
            }
        }
        System.out.println(answer);
    }
}

입력 받은 숫자 카드를 이분 탐색을 통해서 상근이가 가진 카드 중에서 있는지 여부를 판별해서 있으면 1을 출력 없으면 0을 출력하도록 한다.

결과

백준 10816번 숫자 카드 2

문제

나의 풀이

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

public class Main {
    public static int lower_bound(int[] a, int num) {
        int n = a.length;
        int left = 0;
        int right = n - 1;
        int answer = -1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(a[mid] == num) {
                answer = mid;
                right = mid - 1; // 하한
            } else if(a[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
    
    public static int upper_bound(int[] a, int num) {
        int n = a.length;
        int left = 0;
        int right = n - 1;
        int answer = -1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(a[mid] == num) {
                answer = mid;
                left = mid + 1; // 상한
            } else if(a[mid] > num) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return answer;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String line[] = br.readLine().split(" ");
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(line[i]);
        }
        Arrays.sort(a);
        int m = Integer.parseInt(br.readLine());
        line = br.readLine().split(" ");
        StringBuilder answer = new StringBuilder();
        for(int i = 0; i < m; i++) {
            int num = Integer.parseInt(line[i]);
            int left = lower_bound(a, num);
            int right = upper_bound(a, num);
            if(left == -1) {
                answer.append("0 ");
            } else {
                answer.append((right - left + 1) + " ");
            }
        }
        System.out.println(answer);
    }
}

이분탐색의 상한과 하한을 이용하여 해결하면 된다.

결과

백준 11728번 배열 합치기

문제

나의 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line[] = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int a[] = new int[n];
        line = br.readLine().split(" ");
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(line[i]);
        }
        int b[] = new int[m];
        line = br.readLine().split(" ");
        for(int i = 0; i < m; i++) {
            b[i] = Integer.parseInt(line[i]);
        }

        int c[] = new int[n + m];
        {
            int i = 0;
            int j = 0;
            int k = 0;
            while (i < n || j < m) {
                if (j >= m || (i < n && a[i] <= b[j])) {
                    c[k++] = a[i++];
                } else {
                    c[k++] = b[j++];
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n + m; i++) {
            sb.append(c[i] + " ");
        }
        System.out.println(sb);
    }
}

머지 소트에서 배열을 합치는 알고리즘을 구현하면 된다.

결과