프로그래머스 완전탐색 소수 찾기 with Kotlin

프로그래머스 완전 탐색 부분 소수 찾기 문제입니다.

IntelliJ에서의 풀이입니다.

isPrime 참고: https://www.geeksforgeeks.org/sieve-of-eratosthenes/

Sieve of Eratosthenes - GeeksforGeeks

import kotlin.math.log10
import kotlin.math.pow

val numbers: String = "011"

fun solution(numbers: String): Int {
    var answer = 0
    
    var inarr = numbers.map { it.toString().toInt() }.toIntArray().sortedArray()
    // 주어진 문제열을 ASC 정렬된 숫자열로 변환합니다. 
    var maxnum: Int = 0
    for (i in inarr.indices)
        maxnum += 10.0.pow(i.toDouble()).toInt() * inarr[i]
        // 숫자열로 만들 수 있는 최대 숫자를 구합니다.

    var isprime: BooleanArray = BooleanArray(maxnum + 1) { true } // GFG참고
    // 모두 true인 배열을 만든 후, 다른 수의 배수가 되는 수를 false로 바꿔줍니다.
    
    var cnt = 1
    while (cnt * cnt <= maxnum) { // 제곱이 maxnum보다 작으면 안의 for문의 의미가 없습니다.
        cnt++
        if (isprime[cnt]) {
            for (i in cnt * cnt .. maxnum step cnt) // cnt*cnt에서 최대 수까지 cnt만큼 커짐
                if (isprime[i]) isprime[i] = false
        }
    }


    // inarr로 prime number를 만들 수 있으면 answer 증가
    var inarrisused: BooleanArray = BooleanArray(inarr.size) { false }
    // 이미 사용된 Index인지 표시합니다.
    
    var primenum: ArrayList<Int> = ArrayList(inarr.size)
    // Prime number의 각 자리별 숫자를 저장합니다.
    
    var frontnum: Int = 0
    // Prime number의 각 자리별 숫자를 저장하기 위해 
    // 1의 자리 수가 아닌 숫자를 임시로 저장합니다.
    
    var flag = false
    // 해당 Prime number의 자리 숫자가 이미 해결이 되었는지 표시합니다.
    
    for (i in 2 until isprime.size) { // 소수 판별된 배열의 모든 요소에 대해서
        if (isprime[i]) { // 만약 Index가 소수라면, 
        				  // 해당 Index를 Inarr로 만들 수 있는지 확인
                          
            frontnum = i
            while (frontnum >= 1) {
                primenum.add(frontnum % 10)
                frontnum /= 10
            }
            // Index(Prime number)의 자리별 숫자를 primenum에 저장합니다.
            
            primenum.sorted()
            // inarr이 정렬되어있기 때문에 보다 효율을 위해 정렬합니다.
            
            for (k in primenum.indices) { // primenum의 자리별 숫자에 대해
                flag = false
                for (j in inarr.indices) { // inarr의 자리별 숫자를 비교합니다.
                    if (!flag) // 이미 확인된 숫자가 아니고
                        if (primenum[k] == inarr[j] && !inarrisused[j]) {
                            inarrisused[j] = true
                            flag = true
                        } // 두 숫자가 같고, 이미 사용된 숫자가 아니면
                          // inarr is used와 flag를 true로 바꿔서 표시합니다.
                }
            }
            
            cnt = 0 // 사용된 숫자의 개수와 Index(Prime number)의 자릿수를 비교합니다.
            for (i in inarrisused.indices) {
                if (inarrisused[i]) {
                    cnt++
                    inarrisused[i] = false // 재사용을 위해 false로 복구합니다.
                }
            }
            
            if (cnt == 1 + log10(i.toDouble()).toInt()) answer++ 
            // 모든 자릿수를 주어진 숫자열 inarr로 채울 수 있다면
            // 문제 조건을 만족하므로 answer에 1을 더해줍니다.
            
            primenum.clear()
            // 재사용을 위해 비워줍니다.
        }
    }

    return answer
}

fun main() {
    print(solution(numbers)) // 2
}

URL: https://programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기