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

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...분리된 배열의 길이)갯수를 뽑는 순열을 반복해서 구했다.

각 r개씩 뽑는 순열은 재귀 DFS 탐색으로 구했다.

// 내 풀이
import Foundation

var numberArr = [Int]()
var generatedNumber = Set<Int>()
var result = [Int]()
var checkList = [Bool]()

func convArrToNum(_ arr: [Int]) -> Int {
    return arr.reduce(0) { $0 * 10 + $1 }
}

func isPrimeNumber(_ n: Int) -> Bool {
    guard n > 1 else { return false }
    let last = Int(sqrt(Double(n)))
    var count = 0
    var flag = true
    for i in (1...last) {
        if n % i == 0 {
            count += 1
            if count > 1 {
                flag = false
                break
            }
        }
    }
    return flag
}

func permuDFS(phase: Int, r: Int) {
    if phase == r {
        let num = convArrToNum(result)
        generatedNumber.insert(num)
        return
    } else {
        for i in (0..<numberArr.count) {
            if checkList[i] == false {
                result[phase] = numberArr[i]
                checkList[i] = true
                permuDFS(phase: phase + 1, r: r)
                checkList[i] = false
            }
        }
    }
}

func solution(_ numbers:String) -> Int {
    numberArr = numbers.map { Int(String($0))! }
    
    // generatedNumber Set을 완성시킨다
    for i in (1...numberArr.count) {
        result = [Int](repeating: 0, count: i)
        checkList = [Bool](repeating: false, count: numberArr.count)
        permuDFS(phase: 0, r: i)
    }
    
    // generatedNumber Set에서 소수의 갯수를 구한다
    var count = 0
    for element in generatedNumber {
        if isPrimeNumber(element) {
            count += 1
        }
    }
    
    return count
}

// "17" -> [7, 17, 71] -> 3개
// "011" -> [11, 101] -> 2개

let numbers = "011" // 1, 17, 71 == 3
let sr = solution(numbers)
print(sr)

 

다른 사람 풀이

재귀 DFS를 swift 문법에 맞춰서 구한 것 같다. 그리고 solution 함수에서 Set<String>에서 각 String형 원소들을 Int형으로 변환할 때 나오는 옵셔널이 나오는 부분을 compactMap을 사용해서 해소한 부분이 눈에 띄었다(nil제거, 옵셔널 바인딩).

// 다른 사람 풀이
import Foundation

func combinations(_ array: [String]) -> Set<String> {
    if array.count == 0 { return [] }

    let answerArray = (0..<array.count).flatMap { i -> [String] in
        var removedArray = array
        let elem = removedArray.remove(at: i)
        return [elem] + combinations(removedArray).map { elem + $0 }
    }

    return Set(answerArray)
}

func isPrime(_ number: Int) -> Bool {
    guard number > 1 else {
        return false
    }

    for i in 2..<number {
        if number % i == 0 { return false }
    }
    return true
}

func solution(_ numbers: String) -> Int {
    let array = Array(numbers).map{ String($0) }
    let intSet = Set(combinations(array).compactMap { Int($0) })
    return intSet.filter{ isPrime($0) }.count
}