[99클럽 코테 스터디 23일차 TIL] 소수 찾기 - 프로그래머스

어찌보면 이중 완전탐색?

 

https://school.programmers.co.kr/learn/courses/30/lessons/42839

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 
흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 
종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

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

풀이 접근

두 개의 함수가 필요하다고 생각했다.

- 종이 조각의 순서를 갖는 순열 함수

- 소수 판별 함수

먼저 순열 함수는 아래 글을 참고하자.

[Algorithm] Permutation & Combination(순열과 조합)

소수 판별 함수는 에라토스테네스의 체를 활용한다.

func isPrime(n: Int) -> Bool {
    let prime: Set<Int> = [2, 3, 5, 7, 11, 13, 17, 19, 23]
    if prime.contains(n) {
        return true
    }
    if n < 2 || n % 2 == 0 || n % 3 == 0 || n % 5 == 0 {
        return false
    }
    for i in 4...Int(sqrt(Double(n))) {
        if n % i == 0 {
            return false
        }
    }
    return true
}

 

이제 두 함수를 적절히 활용하자.

문자열 내에 동일한 숫자가 여러 개이거나 0이 앞에 와서 같은 숫자가 나오는 경우를 대비하여

소수 판별이 이미 된 숫자인지 확인할 변수가 필요하다.

var cache: Set<Int> = []

문자열의 각 문자를 인덱스로 쉽게 접근하기 위한 변수와 결과 값 변수를 정의한다.

var numbersArray = numbers.map(String.init)
var result = 0

다음은 이중 for문을 이용하는데, 첫 번째 반복은 순열의 길이 1 ~ 문자열의 길이,

두 번째 반복은 각 길이에 해당하는 순열들이다.

for l in 1...numbers.count {
    for p in permutations(data: Array(0...numbers.count-1), count: l)! {
        var temp = ""
        // 순열에 포함된 인덱스로 문자열 조합
        for i in p {
            temp += numbersArray[i]
        }
        // Int로 변환
        let tempNum = Int(temp)!
        
        // 소수 판별을 했던 수라면 넘어가기
        if cache.contains(tempNum) {
            continue
        }
        
        // 소수 판별 후 result에 적용 및 cache에 저장
        result += isPrime(n: tempNum) ? 1 : 0
        cache.insert(tempNum)
    }
}

최종 코드 - Swift

import Foundation

func solution(_ numbers:String) -> Int {
    var cache: Set<Int> = []
    var numbersArray = numbers.map(String.init)
    var result = 0
    for l in 1...numbers.count {
        for p in permutations(data: Array(0...numbers.count-1), count: l)! {
            var temp = ""
            for i in p {
                temp += numbersArray[i]
            }
            let tempNum = Int(temp)!
            if cache.contains(tempNum) {
                continue
            }
            result += isPrime(n: tempNum) ? 1 : 0
            cache.insert(tempNum)
        }
    }
    
    return result
}

func isPrime(n: Int) -> Bool {
    let prime: Set<Int> = [2, 3, 5, 7, 11, 13, 17, 19, 23]
    if prime.contains(n) {
        return true
    }
    if n < 2 || n % 2 == 0 || n % 3 == 0 || n % 5 == 0 {
        return false
    }
    for i in 4...Int(sqrt(Double(n))) {
        if n % i == 0 {
            return false
        }
    }
    return true
}

func permutations<T>(data: [T], count: Int) -> [[T]]? {
    guard data.count >= count else { return nil }
    var result: [[T]] = []
    var buffer: [T] = []
    var visited = Array(repeating: false, count: data.count)
    
    func nextElement() {
        if buffer.count == count {
            result.append(buffer)
            return
        }
        for i in 0..<data.count {
            if !visited[i] {
                visited[i] = true
                buffer.append(data[i])
                nextElement()
                buffer.removeLast()
                visited[i] = false
            }
        }
    }
    nextElement()
    return result
}

최종 코드 - Python3

파이썬에서는 permutations 함수를 따로 작성할 필요가 없었다.

from itertools import permutations
import math

def solution(numbers):
    cache = {}
    result = 0
    for l in range(1,len(numbers)+1):
        for p in permutations(range(len(numbers)),l):
            temp = ""
            for i in p:
                temp += numbers[i]
            temp = int(temp)
            if temp in cache:
                continue
            isPrimeN = isPrime(temp)
            cache[temp] = isPrimeN
            if isPrimeN:
                result += 1
    return result

def isPrime(n):
    prime = set([2,3,5,7,11,13,17,19,23])
    if n in prime: return True
    if n < 2 or n % 2 == 0 or n % 3 == 0 or n % 5 == 0: return False
    for i in range(4,int(math.sqrt(n))+1):
        if n % i == 0: return False
    return True

Conclusion

순열과 소수 판별 모두 완전탐색의 일부이라, 두 가지 완전탐색을 섞어놓은 느낌이다.

Swift기준으로 두 개의 함수를 별도로 작성해서 푸는 문제라 그런지 재밌는 문제였다.