[백준] 10816번 : 숫자 카드 2 - 자바[Java]

10816번: 숫자 카드 2

 

풀이

Map을 사용하면 간단하게 풀 수 있지만, 이분 탐색으로도 풀 수 있다.

다만 이 문제는 배열에 들어가있는 숫자의 개수를 구해야 하는데, 기본적인 이분 탐색 코드는 숫자의 위치(인덱스)만을 구할 뿐, 배열에 중복된 숫자가 있을 경우 숫자의 개수를 구하지는 못한다.

그렇기 때문에 기본적인 이분 탐색 코드를 변형해서 중복된 숫자의 왼쪽 끝 위치(lower bound)와 오른쪽 끝 위치(upper bound)를 구해 중복된 숫자의 개수를 구한다.

    static int upperBound(int[] cards, int num) {	//상한 값
        int left = 0;
        int right = cards.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if (cards[mid] <= num)
                left = mid + 1;
            else if (cards[mid] > num)
                right = mid - 1;
        }

        return right;
    }

    static int lowerBound(int[] cards, int num) {	//하한 값
        int left = 0;
        int right = cards.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if (cards[mid] < num)
                left = mid + 1;
            else if (cards[mid] >= num)
                right = mid - 1;
        }

        return left;
    }

 

코드

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] cards = new int[n];
        for (int i = 0; i < n; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(cards);

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            bw.write((upperBound(cards, num) - lowerBound(cards, num) + 1) + " ");
        }

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

    static int upperBound(int[] cards, int num) {
        int left = 0;
        int right = cards.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if (cards[mid] <= num)
                left = mid + 1;
            else if (cards[mid] > num)
                right = mid - 1;
        }

        return right;
    }

    static int lowerBound(int[] cards, int num) {
        int left = 0;
        int right = cards.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if (cards[mid] < num)
                left = mid + 1;
            else if (cards[mid] >= num)
                right = mid - 1;
        }

        return left;
    }
}

 

번외 - Map을 사용한 풀이

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(st.nextToken());
            bw.write(map.getOrDefault(num, 0)+ " ");
        }

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

 

위가 이분 탐색, 아래가 Map을 이용한 풀이

Reference

• [백준] 10816번 : 숫자 카드 2 - JAVA [자바]