TIL 41일차 (소수 찾기 - Kotiln | 코드카타 잠시 쉽니다)

코드카타

 

소수 찾기

 

문제

 

numbers의 최대길이는 7이므로 조합 가능한 모든 수를 생성해도 시간초과가 나지 않는다.

 

 

입출력 예시

 

주어진 수를 각 자리수별로 나누고 가능한 모든 조합을 생성한 뒤

중복을 제거하기 위해 집합에다 추가한다.

 

생성한 집합의 요소 중 소수에 해당하는 개수를 반환한다.

 

"17" -> [1, 7] -> [1, 7, 17, 71] -> [7, 17, 71] -> 3
"011" -> [0, 1, 1] -> [0, 1, 11, 10, 101, 110] -> [11, 101] -> 2

위와 같은 과정을 통해 주어진 수에서 만들 수 있는 소수개수를 반환한다.

 

 

조합 생성 함수

// str: 현재까지 생성된 숫자 문자열 
// remaing: 아직까지 사용되지 않은 문자들

private fun getCombination(str: String, remaining: List<Char>){
    if(str.isNotEmpty()) set.add(str.toInt())
    
    // 남은 문자들을 순회하면서
    for(i in remaining.indices){
        // 현재 문자를 현재 숫자 문자열에 추가해 새로운 숫자 문자열 생성
        val newStr = str + remaining[i]
        // 현재 문자를 제외한 나머지 문자들로 새로운 리스트 생성
        val newRemaining = remaining.toMutableList()
        newRemaining.removeAt(i)
        // 새로운 숫자 문자열과 남은 문자들로 재귀 호출
        getCombination(newStr, newRemaining)
    }
}

이 함수는 주어진 문자들로 가능한 모든 숫자 조합을 생성하고,

이 숫자들을 set에 추가하는 재귀 함수이다.

 

해당 재귀 함수는 반복문의 각 인덱스별로 다른 숫자 문자열을 만들고,

각 반복마다 remaining 리스트가 빌 때까지 호출된다.

 

 

풀이

class Solution {

    // 가능한 모든 숫자 조합을 저장할 집합
    lateinit var set: MutableSet<Int>

    // 재귀적으로 가능한 모든 숫자 조합 생성
    private fun getCombination(str: String, remaining: List<Char>){
        if(str.isNotEmpty()) set.add(str.toInt())
        for(i in remaining.indices){
            val newStr = str + remaining[i]
            val newRemaining = remaining.toMutableList()
            newRemaining.removeAt(i)
            getCombination(newStr, newRemaining)
        }
    }

    // 소수 판별 함수
    private fun isPrime(num: Int): Boolean {
        if (num <= 1) return false
        return (2..Math.sqrt(num.toDouble()).toInt()).none { num % it == 0 }
    }

    fun solution(numbers: String): Int {
        // 주어진 숫자 문자열을 각 자리수별로 분리
        val digits = numbers.toCharArray().toList()

        // 집합을 초기화하고 가능한 모든 숫자 조합을 넣음
        set = mutableSetOf()
        getCombination("", digits)

        // 생성된 숫자 조합 중 소수의 개수를 세어 반환
        return set.count{ isPrime(it)}
    }
}

 

set은 재귀함수에서 사용되기에 lateinit으로 선언해

main함수에서 초기화할 수 있도록 한다.

 

빈 문자열과 주어진 수의 각 자리수에 해당하는 문자 리스트를

모든 숫자 조합을 생성하는 재귀함수의 인자값으로 넘겨준다.

 

소수 판별 함수를 작성해 초기화 된 집합의 요소 중

소수의 개수를 세서 반환한다.

 

 

회고

보자마자 함수 2개 작성해서 풀면 되겠구나 싶어서

쉬운 문제인 줄 알았는데 생각보다 푸는데 엄청 오래걸린 문제였다.

 

각 자리수의 모든 조합을 생성해야하는 문제인데 부분집합과 순열을 

생성하는 것으로 착각해서 함수 짜는데에 쓸데없이 시간을 많이 소모했다.

 

모든 숫자 조합을 생성하는 함수는 원래 숫자 문자열을 인자로 받아

모든 조합이 들어있는 set을 반환하는 식으로 짰는데 

 

함수 내에 함수가 들어있는게 맘에 안들어 다른 방법을 찾아보니

lateinit으로 set을 선언해 main에서 초기화하는 방법이 있었다.

 

재귀함수는 실행 과정을 머리속에서 그리기가 어려워

나올 떄마다 이해하는데 아주 오래 걸리는 것 같다.

 

 

코드카타 잠시 쉬는 이유

원래 코드카타는 1시간 정도 잡고 푸는건데

문제 난이도가 점점 올라감에 따라 최근에 한 문제 풀고 정리하는데

기본 2 ~ 3시간 걸리고, 오래걸리면 저녁까지 정리하는 경우도 있다.

 

매일 코드카타를 진행함으로써 개발공부에 쏟는 시간이 부족하다고 느꼈고,

지금 안드로이드 개발 관련해서 공부할게 상당히 밀린 상태이다.

 

그렇다고 문제를 빨리 풀기 위해 로직 이해도 제데로 못한 채

문제를 해결하면 코드카타를 하는 의미가 없다고 생각한다.

그래서 밀린 개발 공부를 하기 위해 코드카타를 잠시 쉬기로 결정했다.