백준호 7795호 먹힐까 먹힐까 Kotlin 구현

---

“`

백준호 7795호 먹힐까 먹힐까 Kotlin 구현

“`

이 기사에서 무엇을 배울 것인가

1. 백준솔루션 7795호

---

https://www.acmicpc.net/problem/7795

제7795호 먹느냐 먹히느냐

심해에는 A와 B의 두 가지 생명체가 있습니다.

A는 B를 먹는다.

A는 자신보다 작은 먹이만 먹을 수 있습니다.

예를 들어 A의 크기가 {8, 1, 7, 3, 1}이고 B의 크기가 {3, 6, 1}이면 A는 B를 먹습니다.

www.acmicpc.net

백준 7795호 먹힐 것인가, 먹힐 것인가?

난이도 실버

숫자 A와 B의 두 세트가 주어지면,

문제는 A에 주어진 각 수보다 작은 B의 그룹 수를 세는 것입니다.

---

위 링크로 30분 정도 들어가셔서 해결해주세요.

잘 안 될 경우에만 아래 답변을 봐주시면 감사하겠습니다.

---

각 숫자에 대해

이진 검색을 실행했습니다.

fun main() {
    val inputDto = getInput()
    print(solution(inputDto))
}

fun getInput(): InputDto {
    val testCaseCnt = readln().toInt()

    val dtos = emptyList<TestCaseDto>().toMutableList()
    for (i in 1..testCaseCnt) {
        val size = readln()
        val aCreatures = readln().split(" ").map { k -> k.toInt() }.toList()
        val bCreatures = readln().split(" ").map { k -> k.toInt() }.toList()
        dtos.add(TestCaseDto(aCreatures, bCreatures))
    }
    return InputDto(dtos)
}

data class InputDto(
    val testcaseDtos: List<TestCaseDto>
)

data class TestCaseDto(
    val aCreatures: List<Int>,
    val bCreatures: List<Int>
)

fun executeTestcase(dto: TestCaseDto): Int {
    val aList = dto.aCreatures.sorted()
    val bList = dto.bCreatures.sorted()
    var ans = 0
    for (i in aList.indices) {
        ans += binarySearch(bList, aList, i)
    }
    return ans
}

private fun binarySearch(bList: List<Int>, aList: List<Int>, i: Int): Int {
    var left = 0
    var right: Int = bList.size
    while (left + 1 < right) {
        val mid = (left + right) / 2
        if (aList(i) > bList(mid)) left = mid else right = mid
    }
    var ans = left
    if (aList(i) > bList(left)) ans++
    return ans
}

fun solution(dto: InputDto): String {
    return dto.testcaseDtos.joinToString("\n") { executeTestcase(it).toString() }
}


// https://codemasterkimc./

시험

import org.junit.jupiter.api.Assertions.assertEquals
import org.junit.jupiter.api.Test

internal class MainKtTest {

    @Test
    fun test() {
        assertEquals(
            "7\n1",
            solution(
                InputDto(
                    listOf(
                        TestCaseDto(
                            listOf(8, 1, 7, 3, 1),
                            listOf(3, 6, 1)
                        ),
                        TestCaseDto(
                            listOf(2, 13, 7),
                            listOf(103, 11, 290, 215)
                        ),
                    )
                )
            )
        )
    }
}

읽어 주셔서 감사합니다

당신이 뭔가를 얻기를 바랍니다

오늘도 즐겁게 코딩하시길 바랍니다!
🙂

---