백준 / 10816번 / 숫자 카드 2

[문제]

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

[예제 입력]

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

[예제 출력]

3 0 0 1 2 0 0 2

 

---

 

숫자 카드 2는 "이분 탐색"과 "해시를 사용한 집합과 맵" 태그의 문제이다.

 

그냥 풀려면 시간 초과가 뜨기 때문에,

이분 탐색을 활용해 코드를 짜보려 했는데, 10 10 10 이나 -10 -10 과 같이

같은 수가 여러 개 있는 경우를 처리하기가 꽤 까다로웠다.

이 부분도 다뤄보려고 한다.

 

이 문제를 해결할 수 있는 또 다른 방법은 HashMap을 사용하는 방법이다.

 * HashMap을 이용한 또 다른 문제 : https://gr616.tistory.com/252

 

 

---

[ HashMap 사용 ]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(bf.readLine());
        HashMap<Integer, Integer> hash = new HashMap<>();

        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(st.nextToken());

            if (hash.get(num) == null) { 
                hash.put(num, 1);
            } 
            else { 
                hash.put(num, hash.get(num) + 1);
            }
        }

        int m = Integer.parseInt(bf.readLine());

        st = new StringTokenizer(bf.readLine(), " ");
        for (int j = 0; j < m; j++) {
            int num = Integer.parseInt(st.nextToken());
            sb.append(check(hash, num)).append(' ');
        }
        System.out.println(sb);
    }

    static int check(HashMap<Integer, Integer> hash, int num) {
        if (hash.get(num) != null) {
            return hash.get(num);
        }
        return 0;
    }
}

HashMap을 이용한 코드이다.

HashMap에 key와 value를 저장하는데

 

기존에 hash에 들어있지 않는 값이라면 (hash.get(num) == null) ?

value로 1을,

 

기존에 있는 값이라면 value + 1을 해준다.

(예로, 10이 기존에 2개 있었는데, 또 넣어주려 한다면 key는 10, value는 3이 되는 것이다.)

 

그 후, 찾으려는 숫자가 hash에 있는 지 없는 지 검사하면 된다.

hash.get(num) != null을 통해 hash에 해당 숫자가 있는 경우엔 그 key의 value를 return 하고,

hash에 해당 숫자가 없는 경우엔 0을 return 한다.

 

---

[ 이분 탐색 사용 ]

이번 문제는, 기존의 이분 탐색 문제와는 좀 다르다.

중복 원소의 개수를 알아내야 하기 때문에, 그 부분을 고려해 코드를 짜봐야 한다.

 

중복 원소의 왼족 끝 갑소가 오른쪽 끝 값을 알아내는 방법을 사용해보려 한다.

 (참고 : https://st-lab.tistory.com/267)

 

상근이가 숫자 카드 10을 3개 갖고 있으면,

10이 처음 나오는 인덱스 (가장 왼쪽 인덱스)와 가장 마지막에 나오는 인덱스 (가장 오른쪽 인덱스)를 얻어

구간의 길이를 얻어내는 것이다.

 

lower bound  = 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치

upper bound = 찾고자 하는 값을 초과한 값이 처음으로 나타내는 위치 

 

 => 중복 원소에 대한 길이 = (upper bound - lower bound)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(bf.readLine());
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");

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

        int m = Integer.parseInt(bf.readLine());
        st = new StringTokenizer(bf.readLine(), " ");

        for(int i=0; i<m; i++) {
            int num = Integer.parseInt(st.nextToken());
            sb.append(upperBound(card, num) - lowerBound(card, num)).append(' ');
        }
        System.out.println(sb);
    }

    // num 이상의 값 처음으로 나타내는 위치 반환
    static int lowerBound(int[] card, int num) {
        int start = 0;
        int end = card.length;

        // start와 end 같아질 때 까지
        while(start < end) {
            int idx = (start+end)/2;

            if(card[idx] >= num) {
                end = idx;
            }
            else {
                start = idx + 1;
            }
        }

        return start;
    }

    // num 초과 값 처음으로 나타내는 위치 반환
    static int upperBound(int[] card, int num) {
        int start = 0;
        int end = card.length;

        while(start < end) {
            int idx = (start+end)/2;

            if(card[idx] > num) {
                end = idx;
            }
            else {
                start = idx + 1;
            }
        }
        return start;
    }
}