프로그래머스 Lv. 2 Swift 알고리즘 - 소수 찾기

소수 찾기도 해보고 순열도 풀어봤는데... 이 문제는 요상하게 안풀리더라..!

그래서 마지막 설 연휴인만큼 내 자신과 조금 타협해서 타 블로그 분의 풀이를 참고하였다 ^^

참고한 분의 코드가 정말 상당히 나의 머릿속 논리와 흐름이 같아서 모범답안 같은 느낌으로 가져가고자한다 :)

(참고: https://jeong9216.tistory.com/358)

 

 

 

이 문제를 풀면서 생각한 논리적 흐름

1. 완전탐색 문제인 만큼 모든 경우의 수를 다 고려해야한다.
2. 먼저 주어진 numbers를 String으로 변환한 뒤 순열 방식을 사용하여 나올 수 있는 조합의 경우의 수를 전부 numSet에 insert해준다. (중복값을 제거하기 위한 Set)
3. 순열 방식을 이용하기 위해서 재귀식을 사용하는데 numbers에 있는 값들 중 사용을 했는지 안했는지를 확인하기 위해 visited를 이용한 bool 타입을 이용한다.
4. 이미 사용했으면 true로 바꾼뒤 다시 재귀식을 돌려서 계속 False, False, False, False 인 배열을 T, F, F, F / T, T, F, F ... 이런 식으로 원하는 위치의 값을 경우의 수로 셀 수 있도록 누적해준다.
5. 그렇게 numSet에 누적된 값들을 filter에서 isPrime 메서드를 적용하여 소수인 값들만 count해준다.

 

 

* 코드

import Foundation

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

    for i in 1...nums.count {
        visited = Array(repeating: false, count: nums.count)
        
        permutation([], count: 0, rCount: i)
    }
    
    func permutation(_ numArr: [String], count: Int, rCount: Int) {
        if count == rCount {
            numSet.insert(Int(numArr.joined())!)
            return
        }
        
        for (i, n) in nums.enumerated() {
            if visited[i] {
                continue
            }
            
            var newNumArr = numArr
            newNumArr.append(n)
            
            visited[i] = true
            permutation(newNumArr, count: count+1, rCount: rCount)
            visited[i] = false
        }
    }
    return numSet.filter { isPrime($0) }.count
}

func isPrime(_ num: Int) -> Bool {
    if num < 4 {
        return (num <= 1) ? false : true
    } else {
        for i in 2...Int(sqrt(Double(num))) {
            if num % i == 0 {
                return false
            }
        }
    }
    return true
}

 

 

 

정리(Today I Learned)

1. 재귀가 진짜 헷갈리는 것 같다... 직접 하나하나 예시를 돌려보지 않으면 머리속에서 잘 그려지지가 않는다... 무조건 직접 손으로 재귀를 돌려보는 것이 좋은 것 같다.