한 우물만 파는 기술 블로그

입력 예제

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

풀이

1. 이분법 풀이

fun main() = with(Scanner(System.`in`)){

    val strBuilder = StringBuilder()
    val N = nextInt()
    val array = IntArray(N)

    for (i in 0 until N){
        array[i] = nextInt()
    }

    Arrays.sort(array)

    val M = nextInt()

    for (i in 0 until M){
        val key = nextInt()

        strBuilder.append(upperBound(array, key) - lowerBound(array, key)).append(' ')
    }
    println(strBuilder)
}

fun lowerBound(array: IntArray, key: Int): Int {
    var left = 0
    var right = array.size

    while (left < right){
        val midIndex = (left + right) / 2
        val target = array[midIndex]

        if (key <= target){
            right = midIndex
        } else{
            left = midIndex + 1
        }
    }
    return left
}

fun upperBound(array: IntArray, key: Int): Int {
    var left = 0
    var right = array.size

    while (left < right){
        val midIndex = (left + right) / 2
        val target = array[midIndex]

        if (key < target){
            right = midIndex
        } else{
            left = midIndex + 1
        }
    }
    return left
}

2. HashMap 풀이

fun main() {

    val reader = BufferedReader(InputStreamReader(System.`in`))
    val stringBuilder = StringBuilder()

    val map = HashMap<Int, Int>()

    val N = reader.readLine().toInt()

    var st = StringTokenizer(reader.readLine(), " ")

    for (i in 0 until N) {
        val key = st.nextToken().toInt()
        map[key] = map.getOrDefault(key, 0) + 1
    }

    val M = reader.readLine().toInt()

    st = StringTokenizer(reader.readLine(), " ")
    for (i in 0 until M) {
        val key = st.nextToken().toInt()

        stringBuilder.append(map.getOrDefault(key, 0)).append(" ")
    }

    println(stringBuilder)
}