[KOTLIN] 소수 찾기

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

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

문제 설명

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

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

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.
• numbers는 0~9까지 숫자만으로 이루어져 있습니다.
• "013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers	return
"17"	3
"011"	2

입출력 예 설명

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

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

풀이

1. 입력으로 들어온 문자열을 IntArray 에 저장 한다.

2. 1번에서 저장된 IntArray 에 대해서 문제의 조건에 해당되는 경우이 수를 순열을 이용하여 구한다.

3. 구해진 순열 중 중복을 제거하기 위해서 Set 자료에 저장한다.

4. 소수 조건에 해당 되는 지 확인 후 소수일 경우 answer 값을 증가 시킨다.

코드

import java.util.*

class Solution {
    private val resultList = mutableSetOf<Int>()
    
    fun solution(numbers: String): Int {
        var answer = 0
        // 입력을 IntArray로 저장한다.
        val numList = numbers.map { Character.getNumericValue(it) }.toIntArray()
        // IntArray 를 순열을 이요하여 모든 경우의 수를 구하고 각 수가 소수인지 확인 한다.
        val size = numList.size
        
        for (i in 1..size) {
            val visit = BooleanArray(size)
            val out = IntArray(size) { -1 } // 빈값을 확인하기 위해 초기값을 -1 로 설정 함
            permutation(numList, visit, size, i, 0, out)
        }
        
        resultList.forEach { r ->
            if (isPrime(r)) {
                answer++
            }
        }
        
        
        return answer
    }
    
    private fun isPrime(num: Int): Boolean {
        if (num == 0 || num == 1) return false
        
        if (num == 2) return true
        
        for (i in 2 until num) {
            if (num % i == 0) return false
        }
        
        return true
    }
    
    private fun permutation(list: IntArray, visit: BooleanArray, n: Int, r: Int, depth: Int, out: IntArray) {
        if (depth == r) {
            // 결과 출력
            var result = ""
            
            out.forEach {
                // 결과가 초기값이 아닐 경우에만 저장한다.
                if (it != -1) result += it
            }
            
            resultList.add(result.toInt())
            return
        }
        
        for (i in 0 until n) {
            if (!visit[i]) {
                visit[i] = true
                out[depth] = list[i]
                permutation(list, visit, n, r, depth + 1, out)
                visit[i] = false
            }
        }
    }
}