[프로그래머스] Swift - 소수찾기(Lv.2)

👆문제풀러 가기👆

문제 설명

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

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

 

 

제한사항

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

 

입출력 예

numbers	return
"17"	3
"011"	2

---

풀이 (오답)

func solution1(_ numbers:String) -> Int {
    let cNumbers = numbers.sorted(by: >).map{String($0)}.joined()
    var primeNumbers = [[String]]()
    var result = 0
    
    // 소수 배열 생성
    for num in 2...(Int(cNumbers) ?? 2) {
        if checkPrimeNumber(of: num) {
            primeNumbers.append(String(num).map{String($0)})
        }
    }
    
    for prime in primeNumbers {
        var p = prime
        var numbers = cNumbers.map{String($0)}
        
        // 겹치는 문자 제거
        OutLoop: for i in 0..<numbers.count {
            for j in 0..<p.count {
                if p[j] == numbers[i] {
                    p[j] = ""
                    numbers[i] = ""
                    continue OutLoop
                }
            }
        }
        
        // 빈 문자열일 시 result + 1
        if p.joined() == "" {
            result += 1
        }
    }
    return result
}

// 소수 확인
func checkPrimeNumber(of num: Int) -> Bool {
    if num == 2 || num == 3 { return true }

    var isPrime = true
    var i = 2
    
    while i * i <= num {
        if num % i == 0 {
            isPrime = false
            break
        }
        i += 1
    }
    
    return isPrime
}

첫번째 풀이

1. 모든 숫자 조합을 중복없이 구하기

2. 각 숫자 조합의 소수 판별

이와같은 방식으로 구현해야겠다고 생각했었다.

근데 모든 숫자 조합을 구하는 방법을 도통 모르겠어서 두번째 풀이를 생각했다.

 

두번째 풀이

1. 조합가능한 수 중 가장 큰 수(cNumbers) 구하기

2. 가장 큰 수 이하의 소수 구하기

3. 소수 중 조합가능한 수 구하기

이처럼 풀면 숫자 조합의 중복없이, 몇개 되지 않는 소수 중에서 빠른 연산이 간능할거라 생각했고,

실제로 테스트케이스를 통과했으나, 소수 중에서 조합가능한 수를 찾기가 여간 까다로운게 아니었기에

3중 for문과 map으로 떡칠되어 시간초과의 늪을 벗어날 수 없었다.

그래서 정주는 개발중님의 풀이를 보니, 재귀 방식으로 푸는 것을 확인할 수 있었다.

다른 사람 풀이 [메모리: 16793kb, 최대 시간: 58.55ms]

import Foundation

func solution(_ numbers:String) -> Int {
    let nums = numbers.map { String($0) }
    var visited = [Bool]()
    var numSet = Set<Int>()

    func permutaion(_ numArr: [String], count: Int, rCount: Int) {
        if count == rCount {
            numSet.insert(Int(numArr.joined())!)
            return
        }

        for (idx, value) in nums.enumerated() {
            if visited[idx] {
                continue
            }

            var newNumArr = numArr
            newNumArr.append(value)

            visited[idx] = true

            permutaion(newNumArr, count: count + 1, rCount: rCount)
            visited[idx] = false
        }
    }

    for i in 1...nums.count {
        visited = Array(repeating: false, count: nums.count)
        permutaion([], count: 0, rCount: i)
    }

    return numSet.filter { checkPrime(of: $0) }.count


}


func checkPrime(of num: Int) -> Bool {
    if num < 4 {
        return num <= 1 ? false : true
    } else {
        var isPrime = true
        var i = 2

        while i * i <= num {
            if num % i == 0 {
                isPrime = false
                break
            }
            i += 1
        }

        return isPrime
    }
}

 

5번 테스트케이스의 경우 대충 100배까지 차이나는 것으로 보아, 

기존 코드가 역시 상당히 비효율적이었음을 알 수 있었는데,

생각하긴 쉬운데 그걸 구현하기가 여간 까다로웠던 문제가 아닐 수 없었다..