[Java / Kotlin] 99 클럽 코딩 테스트 스터디 미들러 14일차 - 숫자 카드 2

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

 

[풀이]

전날 풀었던 문제와 동일한 내용이지만 기존에는 배열 비교를 통해 contains() 여부를 조사해서 풀었다면, 이번에는 HashMap 통해 Value 값 축적을 통하여 답을 구해야합니다. 또는 이진 탐색을 활용하여 처리가 가능합니다.

 

먼저 HashMap 활용 자바 코드입니다.

public class Main {
    public static void main(String[] args) throws IOException {
        // Initialize the buffered reader and writer for input and output
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        // Read the first input value n
        int n = Integer.parseInt(reader.readLine());

        // Read the first array of integers inputN
        String[] inputN = reader.readLine().split(" ");
        // Read the second input value m
        int m = Integer.parseInt(reader.readLine());

        // Read the second array of integers inputM
        String[] inputM = reader.readLine().split(" ");

        // Create a map to store the count of each number in inputN
        Map<Integer, Integer> hashMap = new HashMap<>();

        // For each number in inputN, update its count in the map
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(inputN[i]);
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }

        // For each number in inputM, write the count from hashMap or 0 if not present
        for (int i = 0; i < m; i++) {
            int num = Integer.parseInt(inputM[i]);
            writer.write(hashMap.getOrDefault(num, 0) + " ");
        }

        // Flush and close the writer
        writer.flush();
        writer.close();
    }
}

입력을 받아 각각 2개의 배열을 생성하는 것은 동일합니다. 하지만 이번엔 추가로 <Integer, Integet> 구조를 갖는 HashMap을 선언해줍니다. 이제 여기서 2번째 배열을 순회하면서 값이 있다면 기존 값에, 없다면 0부터 시작하여 포함 여부 Count를 체크하면 됩니다.

 

아래는 HashMap 활용 코틀린 코드입니다.

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val n = readLine().toInt()

    val inputN = readLine().split(" ").map {it.toInt()}

    val m = readLine().toInt()

    val inputM = readLine().split(" ").map {it.toInt()}

    val hashMap = HashMap<Int,Int>()
    
    repeat(n) {
        hashMap[inputN[it]] = hashMap.getOrDefault(inputN[it],0) + 1
    }

    repeat(m) {
        bw.write("${hashMap[inputM[it]] ?: 0} ")
    }

    bw.flush()
    bw.close()
}

 

이번엔 이진 탐색으로 풀어보겠습니다. 자바 코드와는 크게 차이가 없어서 알고리즘 이해 및 코틀린 코드로만 진행하겠습니다.

이진 탐색은 배열 내부에서 특정한 값을 찾아내는 알고리즘입니다.

1. 배열 중간에 있는 값을 선택하여 찾으려는 값과 비교

2. 찾으려는 값이 중간 값보다 작으면 중간 값을 기준으로 좌측 데이터들을 대상으로 1번부터 retry

3. 찾으려는 값이 중간 값보다 크면 중간 값을 기준으로 우측 데이터들을 대상으로 1번부터 retry

 

중요한 것은 이런 알고리즘을 적용하기 위해서는 사전에 대상 전체 배열이 정렬되어 있어야 합니다.

코틀린 코드로 알고리즘을 구현해보면

fun binarySearch(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.lastIndex
    var mid: Int

    while (low <= high) {
        mid = (low + high) / 2

        when {
            arr[mid] == target -> return mid
            arr[mid] > target -> high = mid - 1
            else -> low = mid + 1
        }
    }
    return -1
}

arr [mid]가 타깃과 동일한 값이면 그대로 반환합니다.

타깃 값이 중간 값보다 작으면 high 값을 중간 값의 -1로 변경합니다. 즉 좌측 데이터들을 대상으로 Search 하게 됩니다.

타겟 값이 중간 값보다 크면 high 값을 중간 값의 +1로 변경합니다. 즉 우측 데이터들을 대상으로 Search하게 됩니다.

 

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {

    fun lowerBound(cards: List<Int>, target: Int): Int {
        var left = 0
        var right = cards.size

        while (left < right) {
            val mid = (left + right) / 2
            if (cards[mid] >= target) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    fun upperBound(cards: List<Int>, target: Int): Int {
        var left = 0
        var right = cards.size

        while (left < right) {
            val mid = (left + right) / 2
            if (cards[mid] > target) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }

    val n = readLine().toInt()
    val cards = readLine().split(" ").map { it.toInt() }.sorted()
    val m = readLine().toInt()
    val queries = readLine().split(" ").map { it.toInt() }

    val result = StringBuilder()

    for (query in queries) {
        val lowerBound = lowerBound(cards, query)
        val upperBound = upperBound(cards, query)
        result.append("${upperBound - lowerBound} ")
    }

    println(result)
}