소수 찾기 - kotlin

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

String을 받고 각 숫자문자로 부분집합을 만들어 소수인지 판별하는 문제다.

풀이 과정

우선 여러 과정이 필요한 만큼 헷갈리지 않게 구분하는 것이 중요하다고 생각했다.
문자열을 list로 바꿔주면 부분집합을 만들어주는 재귀함수, 소수인지 판별해주는 함수를 각각 만들어 줬다.

fun subSet(inputList: List<String>): List<List<String>> {
    if (inputList.isEmpty()) return listOf(emptyList())

    val element = inputList[0]
    val rest = inputList.subList(1, inputList.size)

    val subsetsWithoutElement = subSet(rest)
    val subsetsWithElement = subsetsWithoutElement.map { it + element }

    return subsetsWithoutElement + subsetsWithElement
}

재귀함수를 통해 부분집합을 생성하는 함수

fun checkPrimeNumber(checkNumber: Int): Boolean {
    when (checkNumber) {
        0 -> return false
        1 -> return false
        2 -> return true
        else ->
            for (i in 2..checkNumber / 2 + 1) {
                if (checkNumber % i == 0) return false
            }
    }
    return true
}

숫자가 소수인지 판별해주는 함수.
효율성을 위해 변수를 두지 않고 1과 2만 따로 판별해줬다.

fun solution(numbers: String): Int {
    var answer = 0

    subSet(numbers.map { it.toString() }).forEach {
        if (it.isEmpty()) return@forEach
        if (checkPrimeNumber(it.joinToString("").toInt())) answer++
    }

    return answer
}

프로세스를 실행하는 메인 함수
그러나 입력에 "17"을 넣으면 (1), (7), (1, 7) 은 검색되지만 (7, 1)이 검색되지 않았다.
다른 방법을 통해 모든 경우의 수를 검색하는 방법을 생각해봤다.

1차 수정 (정확성)

set을 활용해 모든 경우의 부분집합을 생성해줬다.

lateinit var numberSet: MutableSet<Int>

fun combinatorNumber(numbers: String, result: String) {
    if (result.isNotEmpty()) numberSet.add(result.toInt())
    if (numbers.isEmpty()) return
    numbers.forEachIndexed { index, c ->
        combinatorNumber(numbers.removeRange(index..index), c.plus(result))
    }
}

main에서 set을 선언해주고 count를 통해 수를 파악해주었다.

lateinit var numberSet: MutableSet<Int>

fun checkPrimeNumber(checkNumber: Int): Boolean {
    when (checkNumber) {
        0 -> return false
        1 -> return false
        2 -> return true
        else ->
            for (i in 2..checkNumber / 2 + 1) {
                if (checkNumber % i == 0) return false
            }
    }
    return true
}

fun combinatorNumber(numbers: String, result: String) {
    if (result.isNotEmpty()) numberSet.add(result.toInt())
    if (numbers.isEmpty()) return
    numbers.forEachIndexed { index, c ->
        combinatorNumber(numbers.removeRange(index..index), c.plus(result))
    }
}

fun solution(numbers: String): Int {
    numberSet = mutableSetOf()
    combinatorNumber(numbers, "")
    return numberSet.count { checkPrimeNumber(it) }
}

해당 코드를 통해 해결할 수 있었다.