1️⃣ 문제
문제 설명
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
- numbers는 길이 1 이상 7 이하인 문자열입니다.
- numbers는 0~9까지 숫자만으로 이루어져 있습니다.
- “013”은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
| numbers | return |
|---|---|
| “17” | 3 |
| “011” | 2 |
2️⃣ 풀이 방법
- depth 길이가 문자열 길이를 넘기지 않을 때까지, 숫자조합 dfs로 탐색
- 선택한 piece는 arr에서 지우고 dfs에 넘겨져야 중복조합(같은 위치의 같은 숫자가 중복되는)이 되지 않는다.
- 다른 인덱스끼리 조합했어도 동일한 조합 존재할 수 있으므로, [Int]를 Set
로 변환하여 중복숫자들을 제거 - 함수 isPrimeNumber()를 이용하여 소수인지 판별 후, 맞으면 answer++
3️⃣ 코드
import Foundation
var size = 0
var combinations: [Int] = []
func isPrimeNumber(_ num: Int) -> Bool {
if num <= 1 { return false }
for i in 2..<num {
if num % i == 0 { return false }
}
return true
}
func dfs(_ arr: [String], _ depth: Int, _ value: String) {
if size > depth {
var arrCopy = arr
for i in 0..<arr.count {
let piece = arrCopy[i]
arrCopy.remove(at: i)
combinations.append(Int(value + piece)!)
dfs(arrCopy, depth + 1, value + piece)
arrCopy.insert(piece, at: i)
}
}
}
func solution(_ numbers:String) -> Int {
size = numbers.count
let numsArray = numbers.map { String($0) }
// 1. dfs로 모든 숫자 조합 찾기
dfs(numsArray, 0, "")
// 2. 중복 숫자들을 제거 하기 위해 Array<Set>로 변환
let combSet = Array(Set(combinations))
// 3. 소수 판별
let answer = combSet.filter { isPrimeNumber($0) }.count
return answer
}
4️⃣ 이 문제를 풀면서 되새긴 점
Set(Array)하면 바로 유일한 값들만 남는다.
let combSet = Array(Set(combinations))