[백준] #10816 숫자 카드2

BOJ #10816
https://www.acmicpc.net/problem/10816

📃 문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

📥 입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

📤 출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

💡 접근

어찌됐건 배열에서 같은 수 찾는 것이니까 이분탐색

문제는 같은 수가 있다는 것.

• 오름차순 정렬하면 일단 같은 수는 모여있을 것이기 때문에 시작 인덱스 값과 끝 인덱스 값을 구해서 서로 빼주면 같은 수가 나올 것

그렇게 아래와 같이 코드를 짰다.

import java.util.*;

public class B10816 {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i=0; i<n; i++) a[i] = sc.nextInt();

        Arrays.sort(a);

        int m = sc.nextInt();
        int b[] = new int[m];
        int result[] = new int[m];
        for(int i=0; i<m; i++){ 
            b[i] = sc.nextInt();
            result[i] = find(a, b[i], n);
        }

        for(int i = 0; i<result.length-1; i++) {
            System.out.print(result[i]+ " ");
        }
        System.out.print(result[m-1]);
        sc.close();
    }

    private static int find(int[] a, int n, int length) {
        int left = findLeft(a, 0, length, n);
        int right = findRight(a, 0, length, n);
        return right - left;
    }

    private static int findLeft(int[] a, int left, int right, int num) {
        int index = (left + right) / 2;
        if(left >= right) {
            return index;
        }
        if(a[index] >= num) {
            return findLeft(a, left, index, num);
        }else {
            return findLeft(a, index+1, right, num);
        }
    }

    private static int findRight(int[] a, int left, int right, int num) {
        int index = (left + right) / 2;
        if(left >= right) {
            return index;
        }
        if(a[index] <= num) {
            return findRight(a, index+1, right, num);
        }else {
            return findRight(a, left, index, num);
        }
    }
}

처음에 이렇게 짜서 제출했는데 시간초과가 났다...
대체 왜,,,????? Scanner를 BufferReader로 바꾸고 해도 시간초과 난다....
아,,,,,,,, 어디서 잘못된거지,,
했는데

출력할 때 StringBuilder로 바꿔줬는데 됐다..🙄

📍 코드

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

public class B10816 {
    public static void main(String args[]) throws Exception {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(rd.readLine());
        String[] prea = rd.readLine().split(" ");

        int m = Integer.parseInt(rd.readLine());
        String[] preb = rd.readLine().split(" ");

        int a[] = new int[n];
        int b[] = new int[m];

        for(int i=0; i<prea.length;i++) a[i] = Integer.parseInt(prea[i]);
        for(int i=0; i<preb.length;i++) b[i] = Integer.parseInt(preb[i]);
        
        Arrays.sort(a);
        StringBuilder sb = new StringBuilder();
		for (int num : b) {
			sb.append(find(a, num, n)).append(" ");
		}
		System.out.println(sb.toString());
    }

    private static int find(int[] a, int n, int length) {
        int left = findLeft(a, 0, length, n);
        int right = findRight(a, 0, length, n);
        return right - left;
    }

    private static int findLeft(int[] a, int left, int right, int num) {
        int index = (left + right) / 2;
        if(left >= right) {
            return index;
        }
        if(a[index] >= num) {
            return findLeft(a, left, index, num);
        }else {
            return findLeft(a, index+1, right, num);
        }
    }

    private static int findRight(int[] a, int left, int right, int num) {
        int index = (left + right) / 2;
        if(left >= right) {
            return index;
        }
        if(a[index] <= num) {
            return findRight(a, index+1, right, num);
        }else {
            return findRight(a, left, index, num);
        }
    }
}

역시 DP는 Bottom up이 편하다.