Programmers[소수찾기]

문제

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

내 생각

완전탐색의 전형적인 유형이다.
전부 다 해보고 그 중 되는 것들의 갯수를 세어 결과를 반환하는 방법으로 코드를 작성했다.

깨달은 점

BooleanArray를 사용한 checking 되는 방법은 잊지않고 상기시켜야 할 거 같다.
재귀 공부는 꾸준히...재귀 공부는 꾸준히...재귀 공부는 꾸준히...
또한 소수 판별을 할 때 Count 변수로 세면 시간초과가 뜬다. 나눠지는 수가 존재했을 때 false가 반환되는 함수 형태로 고쳐서 했더니 바로 문제를 해결할 수 있었다.

코드

class Problem2 {
    private val numberSet = mutableSetOf<Int>()
    lateinit var tempNumbers: String
    lateinit var check: BooleanArray

    fun solve(numbers: String): Int {
        var answer = 0
        tempNumbers = numbers
        check = BooleanArray(tempNumbers.length)

        func(0, "")
        answer = numberSet.size
        return answer
    }

    fun func(depth: Int, strNum: String) {
        if (depth == tempNumbers.length) {
            var counter = 0
            if (strNum == "") return
            val number = strNum.toInt()
            if (number == 0) return
            if (number == 1) return

            if(isPrime(number)){
                numberSet.add(number)
            }
            return
        }

        for (i in tempNumbers.indices) {
            if (!check[i]) {
                check[i] = true
                func(depth + 1, strNum + tempNumbers[i])
                check[i] = false
                func(depth + 1, strNum)
            }
        }
    }

    fun isPrime(number : Int) : Boolean{
        for(i in 2 until number){
            if(number % i == 0) return false
        }
        if(number <= 1) return false

        return true
    }
}

좋은 웹페이지 즐겨찾기