[Swift] [75일차] 소수만들기_프로그래머스

소수만들기 - S/W coding test

---

문제 설명

1. 숫자 배열이 주어진다.
2. 여기서 3개 골라서 소수가 되는 경우의 수 구하기

---

문제 풀이

1. 이거 일단 숫자 개수가 최대 50개라고 되어있어서 완전탐색으로 해도 될 것 같았다.

for i in 0 ..< LEN - 2 {
        for j in i+1 ..< LEN - 1 {
            for k in j+1 ..< LEN {
                print(i, j, k)
            }
        }
    }

이렇게 구성했을 때 값은

0 1 2
0 1 3
0 2 3
1 2 3

이렇게 nC3 잘뽑아준것을 확인할 수 있다. 이걸 다 더해서 일단 candidate_arr에 모아주고, 그걸 이제 소수 판단 함수로 솎아주면 될 것 같다.

2. 소수판단 is_prime()함수 만들기

func is_prime(_ n: Int) -> Bool {
    for i in 2 ... Int(sqrt(Float(n))) {
        if n % i == 0 {
            return false
        }
    }
    return true
}

<에라토스 테네스의 체> 사용해서 제곱근에 도달할 때까지 i로 나눠줘서 그래도 안걸러진 친구는 소수임이 true로 나오는 로직이다.

최종코드

import Foundation

func is_prime(_ n: Int) -> Bool {
    for i in 2 ... Int(sqrt(Float(n))) {
        if n % i == 0 {
            return false
        }
    }
    return true
}

func solution(_ nums: [Int]) -> Int {
    let LEN = nums.count

    var candidate_arr = [Int]() // 소수 후보군 (계산 값들 모아놓은 배열 )
    for i in 0 ..< LEN - 2 {
        for j in i+1 ..< LEN - 1 {
            for k in j+1 ..< LEN {
                candidate_arr.append(nums[i]+nums[j]+nums[k])
            }
        }
    }
    return candidate_arr.filter { is_prime($0) }.count
}

---

채점 결과

정확성: 100.0
합계: 100.0 / 100.0
뭔가 구성이 깔끔하게 풀린것 같아서 맘에 들었다.

타인의 코드

import Foundation

func solution(_ nums:[Int]) -> Int {

    func isPrime(_ num: Int) -> Bool {
        var n = 2
        while n < num {
            if num % n == 0 { return false }
            n += 1
        }
        return true
    }

    var answer = 0

    for i in 0 ..< nums.count - 2 {
        for j in i + 1 ..< nums.count - 1 {
            for k in j + 1 ..< nums.count {
                if isPrime(nums[i] + nums[j] + nums[k]) { answer += 1 }
            }
        }
    }
    return answer
}

사실상 동일한 코드였다. 살짝 다른게 있으면 굳이 배열에 안모아주고 바로 isPrime을 적용시켜서 풀어줬다는 부분 정도?
그리고 2...N-1 까지를 범위로 잡았는데, 그것보다는 이게 소수가 가장크게 나줘지는게 자기 자신이라, 루트값까지 범위를 해줘도 괜찮기 때문에 양쪽 좋은점 잘 합치면 좋은 코드가 될 것 같다.

개선코드

import Foundation

func is_prime(_ n: Int) -> Bool {
    for i in 2 ... Int(sqrt(Float(n))) {
        if n % i == 0 {
            return false
        }
    }
    return true
}

func solution(_ nums: [Int]) -> Int {
    let LEN = nums.count
    var answer = 0
    for i in 0 ..< LEN - 2 {
        for j in i+1 ..< LEN - 1 {
            for k in j+1 ..< LEN {
                if is_prime(nums[i]+nums[j]+nums[k]) {
                    answer += 1
                }
            }
        }
    }
    return answer
}