[Swift]프로그래머스_소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

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

예시

"1234"가 주어졌을 경우엔, "1", "2", "3", "4" 네 가지의 숫자로 만들 수 있는 소수의 개수를 출력하는 문제이다. 

 

풀이

아직 제대로 공부를 하지 않은 채로 풀어서 굉장히 어려웠다. 먼저 두 가지 문제를 해결해야한다. 

 

1) 만들 수 있는 모든 수를 구해야한다.

2) 위에서 구한 수가 소수인지 판별해야한다. 

 

만들 수 있는 모든 수를 어떻게 구할 지에 대해 굉장히 오래걸렸다. 아무리 생각해도 생각이 나지 않아 검색해보고 참고하여 문제를 진행하였다. 참고해서 알아본 결과, DFS 알고리즘을 이용하여 깊이에 따라 자리수에 알맞는 수를 구할 수 있었다. 분명 다음에도 탐색 문제를 풀 때 비슷한 경우가 있을 것이므로 기억해둬야겠다. 

 

소수를 판별하기 위해 처음에는 에라토스테네스의 체를 사용하려고했다. 하지만 생각해보니 이를 이용해 소수의 개수를 세려면 백만개의 배열 원소를 전부 확인해야한다. 또한 수를 구한 뒤 그 수만 소수인지 아닌지 판별하면 되므로 구한 숫자의 제곱근까지 나누어보아 나머지가 0인 경우가 있으면 소수가 아니라고 판단하도록 하였다. 

 

아래에 코드와 함께 설명을 조금 더 해보겠다. 

import Foundation

func solution(_ numbers:String) -> Int {

    let numArr = numbers.map {String($0)}
    var strNumArr: [String] = []
    var numCheck = [Int](repeating: 0, count: numArr.count)
    var number = ""
    var primeBool = true
    var result: [Int] = []

    for i in numArr {
        strNumArr.append(i)
    }
    strNumArr = strNumArr.sorted {$0 < $1}
    //소수 확인
    func isPrime(_ number: Int) {
        if number == 2 || number == 3 || number == 5 {
            primeBool = true
        } else if number == 0 || number == 1 {
            primeBool = false
        } else {
            for i in 2...Int(sqrt(Double(number))) {
                if number % i == 0 {
                    primeBool = false
                    break
                }
            }
        }
    }

    // 숫자 만드는 함수
    func DFS(_ depth: Int, _ numStr: String, _ count: Int) { 
        if depth == count {
            if let number = Int(number) {
                isPrime(number)
                if primeBool == true && !result.contains(number) {
                    result.append(number)
                }
                primeBool = true
            }
        } else { 
            for i in 0..<numArr.count {
                if numCheck[i] == 0 {
                    number += numArr[i]
                    numCheck[i] = 1
                    DFS(depth + 1, number, count)
                    numCheck[i] = 0
                    number = numStr
                }
            }
        }
    }
    for i in 1...strNumArr.count {
        DFS(0, "", i)
    }
    return result.count
}

일단 숫자를 붙여서 새로운 수를 만드는 것이 더 간편하다고 생각했기 때문에 String으로 진행하기로 하였다. 따라서 먼저 주어진 문자열을 map메서드를 이용해 하나의 Character로 만들어주었다. 

 

모든 숫자를 구한 방법에 대해 정리해보겠다. 다른 분의 코드를 참고하여 작성한 것이라 전부 직접 생각해서 작성한 코드는 아니지만 어떤 방식으로 구현되는지 정리하며 내 것으로 만들려고 노력해보자.

일단 전체적인 구조부터 보자. DFS함수 다음에 for문을 이용해 문자열의 숫자만큼 반복해준다. 이는 한자리수부터 가장 큰 자리수까지 수를 구한다는 것을 의미한다. 

DFS함수의 내부를 보면 재귀적으로 구현하였다. 가장 처음에 depth는 0, count는 1로 들어간다. 즉, 한 자리 수들을 구하겠다는 의미이다. 모든 숫자들을 사용해야하므로 마찬가지로 for문을 이용해 전부 사용할 수 있도록 해주었다. 

숫자를 사용했으면 숫자가 담긴 배열과 동일한 크기의 배열을 통해 해당 숫자가 사용되었는지 확인하여 중복 사용을 막아준다. 해당 원소를 1로 바꿔주어 사용했다고 표시한 뒤 depth에 1을 더하여 다시 DFS함수를 호출한다. 이때 count는 1이므로 바로 depth와 같아지게된다. 마찬가지로 만약 count가 1이 아니라면 DFS가 반복적으로 호출되어 자리수를 나타내는 count의 값에 맞게 뒤에 한자리씩 추가된다. 

 

예를 들어보자. 만약 count가 2이고 문자열은 "123"이라고 생각해보자. 가장 처음에 DFS(0,"",1)이 호출된다. 그렇게되면 number에는 가장 처음 수인 1이 들어가 "1"이 될 것이고 1이 사용됐으므로 numCheck는 [1,0,0]이 될 것이다. 그 뒤 이어서 DFS(1,"1",2)가 실행된다. 이때 1은 이미 사용됐으므로 넘어가고 2가 추가되어 number는 "12"가 된다. 이 다음에 DFS(2,"12",2)가 실행된다면 depth와 count가 동일하므로 소수인지 확인 후 맞다면 result에 추가되고, 아니라면 이어서 진행하는 구조이다. 

 

결론

아직 제대로 알고리즘을 공부하지않고 문제를 풀다보니 접근 방식을 모르는 경우가 많은 것 같다. 이렇게 문제를 풀다가 사용되는 알고리즘들을 하나씩 정리해가며 지식을 쌓아야겠다.