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

https://programmers.co.kr/learn/courses/30/lessons/42839?language=swift

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

level 2 dfs(완전 탐색)

한자리 숫자 여러개로 이루어진 문자열이 주어지고, 종이 조각 하나에 한자리 숫자가 적혀서 흩어져있는 상황이다.

이들을 적절히 조합하여 만들 수 있는 소수의 개수를 반환하는 문제.

즉, 문자열 -> 한자리 숫자들의 배열. 로 만들고 숫자들의 가능한 순열을 구해야 한다.

그렇게 나온 수를 소수인지 아닌지 판별하여 counting 하면 끝

 

접근방법

1. 문자열을 정수의 배열로 변환해준다.

2. 만들어지는 수의 길이를 1부터 배열의 크기만큼 늘려가면서 모든 경우를 구해나간다.

2-1. 길이가 len인 경우의 수를 구하는 방식은 dfs 함수를 사용하여 구한다.

2-2. len만큼의 길이인 수가 만들어지면 소수인지 아닌지 판단하여(isPrime 함수) 소수이면, resultSet (Set 컬렉션 타입)에 insert한다.

3. resultSet의 크기를 반환한다.

 

dfs 함수

구현한 방식은 처음 dfs를 시작할 때,

배열의 모든 원소를 각각 루트노드로 하는 트리가 만들어지도록 dfs를 배열의 모든 요소에 대해서 호출해줬다. (solution 함수의 for 문)

visit[] 배열을 사용하여 각 숫자의 방문 여부를 확인했다.

dfs함수를 호출할 때는 한 노드를 방문한 상태이다.

dfs(numberArray[start], 1, len)는 지금 내가 만들고 있는 숫자는 numberArray[start]이고, 현재 길이는 1이고, 만들어야할 수의 자리수는 len이라는 의미이다. start인덱스의 숫자를 이미 방문한 것이기 때문에 dfs를 호출하기 전에 visit[start]를 true로 바꿔줬다.

그리고 dfs를 호출한 후에 visit[start]를 false로 바꿔준다. 트리에서 같은 레벨의 다른 노드를 방문하는 경우는 독립적인 것이기 때문에 다른 경우의 수에 해당하는 방문 여부가 반영되면 안된다.

그리고 dfs함수 안에서 맨 처음에 길이를 충족했는지 검사한다. 충족했으면 결과값이 소수인지 확인하여 여부에 따라 resultSet에 추가된다.

 

첫자리가 0인 경우도 고려해야해서(011 == 11) 자릿수를 늘려가는 계산을 했다. (result를 갱신하는 식)

중복된 경우도 다 하나의 수로 취급해야해서 Set을 사용했다.

 

말이 길었다..

 

*

소수구하는 함수에서 최악의 경우 num 이전의 수까지 모두 나누어야하는데

원래 제곱근까지로 범위를 제한하지만 제곱근을 구하는데에 더 비용이 클 수도 있지 않을까..싶어서

num 이전으로 범위를 제한했는데 통과는 됐다. 

에라토스테네스의 체를 쓰기에는 귀찮은. 적합한 것 같지도 않고 (변명 주절주절)

 

소스코드

import Foundation

var numberArray:[Int] = []
var n:Int = 0
var resultSet:Set<Int> = []
var visit:[Bool] = Array(repeating: false, count: 7)

func isPrime(_ num:Int) -> Bool {
    if num < 2 {
        return false
    }
    for d in 2..<num {
        if num % d == 0 {
            return false
        }
    }
    return true
}

func dfs(_ result:Int, _ cnt:Int, _ len:Int){
    if cnt == len {
        if isPrime(result) {
            resultSet.insert(result)
        }
    } else {
        for j in 0..<n {
            if !visit[j] {
                visit[j] = true
                dfs(result*10 + numberArray[j], cnt+1, len)
                visit[j] = false
            }
        }
    }
}
func solution(_ numbers:String) -> Int {
    numberArray = Array(numbers).map { $0.wholeNumberValue ?? 0 }
    n = numberArray.count
    
    for len in 1...n {
        dfs(0, 0, len)
    }

    return resultSet.count
}