프로그래머스 소수찾기 Level 2 Swift

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

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

입출력 예

numbers	return
17	3
011	2

풀이: 우선 numbers가 주어졌을 경우 모든 조합을 찾기 위해서는 이러한 과정이 필요하다.

ex) numbers가 123456일경우

차례로 맨 앞자리에 숫자들을 대입하면서 n-1의 자리 숫자들을 뒤에 배치한다.

- 1 2 3 4 5 6

- 11 12 13 14 15 16 , 21 22 23 24 25 26 .... 66

- 111 112 113 114 116 121 122 123 124 125 126 .... 666

이렇게 모든 숫자들을 나열하면 문제가 생기는데

11, 111 222 666과 같이 숫자는 하나만 있는데 조합상엔 여러 숫자가 있는 것이다.

이 문제를 해결하기 위해 맨 처음 numbers에 각 숫자들이 몇개 있는지(중복이 있는지)를 찾는다.

그리곤 조합 상의 숫자가 그 숫자보다 많은 것은 추가해주지 않고 적거나 같은 것들을 추가해줍니다.

중복을 없애기 위해 Set를 사용해준 뒤 그렇게 걸러져 나온 숫자들을 소수가 맞는지 확인해줍니다.

import Foundation
 
func solution(_ numbers:String) -> Int {
    var answer = 0
    let map = numbers.compactMap{String($0)}
    var overlap2 = [String:Int]()
    var overlap1 = [String]()
    var set:Set<Int> = []
    
    //숫자 중 중복이 있는지 찾기
    for i in map {
        set.insert(Int(i)!)
        if overlap1.contains(i){
            overlap2[i]! += 1
            continue
        }
        overlap2[i] = 1
        overlap1.append(i)
    }
    
    //숫자 모든 조합
    var array = Array(repeating: [String](), count: numbers.count)
    array[0] = map
    if numbers.count > 1 {
        for i in 1...numbers.count-1{
            for j in 0..<array[i-1].count{
                for k in 0..<numbers.count{
                    let a = "\(map[k])\(array[i-1][j])"
                    if a.map({String($0)}).filter({$0 == map[k]}).count <= overlap2[map[k]]!{
                        array[i].append(a)
                        set.insert(Int(a)!)
                    }
                }
            }
        }
    }
    
    //소수 찾기
    for n in set{
        var count = 0
        if n == 1 || n == 0{
            continue
        }
        for i in 2...n{
        if n%i == 0{
            count += 1
            if count > 1{
                break
            }
            }
        }
        if count == 1 {
            answer += 1
        }
    }
    return answer
}