[24/3/6] 소수 만들기

🍄 코딩테스트
코딩테스트 문제 풀이

✍🏻 Github

문제 풀이 github 링크

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

nums	result
[1,2,3,4]	1
[1,2,7,6,4]	4

입출력 예 설명

입출력 예 #1

[1,2,4]를 이용해서 7을 만들 수 있습니다.

입출력 예 #2

[1,2,4]를 이용해서 7을 만들 수 있습니다.

[1,4,6]을 이용해서 11을 만들 수 있습니다.

[2,4,7]을 이용해서 13을 만들 수 있습니다.

[4,6,7]을 이용해서 17을 만들 수 있습니다.

---

문제 풀이

나의 풀이

첫번째 풀이는 시간초과로 인한 오답이 떴다.

func calculaterPrimeNumber(_ n: Int) -> Bool {
    (1...n).filter{ n % $0 == 0 }.count == 2
}

시간을 조금더 줄이기 위해서 소수를 푸는 함수에서 1과 자기자신의 비교를 빼고 진행하였다.

import Foundation

func solution(_ nums:[Int]) -> Int {
    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 {
                answer += calculaterPrimeNumber(nums[i] + nums[j] + nums[k]) ? 1 : 0
            }
        }
    }
    return answer
}
func calculaterPrimeNumber(_ n: Int) -> Bool {
    (2..<n).filter{ n % $0 == 0 }.count == 0
}

테스트 1 〉	통과 (44.99ms, 16.4MB)
테스트 2 〉	통과 (65.09ms, 16.1MB)
테스트 3 〉	통과 (12.67ms, 16.3MB)
테스트 4 〉	통과 (9.13ms, 16.4MB)
테스트 5 〉	통과 (67.15ms, 16.6MB)
테스트 6 〉	통과 (861.58ms, 16.5MB)
테스트 7 〉	통과 (24.79ms, 16.5MB)
테스트 8 〉	통과 (1621.68ms, 16MB)
테스트 9 〉	통과 (136.97ms, 16.3MB)
테스트 10 〉	통과 (2041.98ms, 16.3MB)
테스트 11 〉	통과 (3.24ms, 16.3MB)
테스트 12 〉	통과 (0.86ms, 16.2MB)
테스트 13 〉	통과 (2.38ms, 16.4MB)
테스트 14 〉	통과 (0.96ms, 16.3MB)
테스트 15 〉	통과 (0.69ms, 16.1MB)
테스트 16 〉	통과 (6212.07ms, 16.6MB)
테스트 17 〉	통과 (7658.00ms, 16.4MB)
테스트 18 〉	통과 (47.01ms, 15.9MB)
테스트 19 〉	통과 (0.90ms, 16.1MB)
테스트 20 〉	통과 (7668.19ms, 16.4MB)
테스트 21 〉	통과 (6374.08ms, 16.3MB)
테스트 22 〉	통과 (1427.69ms, 16.3MB)
테스트 23 〉	통과 (0.07ms, 16.2MB)
테스트 24 〉	통과 (6291.97ms, 16.4MB)
테스트 25 〉	통과 (6818.84ms, 16.5MB)
테스트 26 〉	통과 (0.07ms, 16MB)

소수를 찾기 위해서 어쩔 수 없이 반복문을 돌아야하는데 이를 줄일 방법을 더 찾아보기 위해서 고민을 해보았지만, 떠오르는 게 없었다.

유클리드 호제법은 약수의 개수를 찾기 위해서 사용했던 것 같은데.. 소수에도 적용이 가능하냐는 고민을 했던거 같다.

for문을 forEach로 바꾸면 조금 더 시간을 줄일 수 있으려나..?

import Foundation

func solution(_ nums:[Int]) -> Int {
    var answer = 0
    let numCount = nums.count
    
    (0..<numCount-2).forEach{ a in
        (a+1..<numCount-1).forEach{ b in
            (b+1..<numCount).forEach { c in
                answer += calculaterPrimeNumber(nums[a] + nums[b] + nums[c]) ? 1 : 0
            }
        }
    }

    return answer
}
func calculaterPrimeNumber(_ n: Int) -> Bool {
    (2..<n).filter{ n % $0 == 0 }.count == 0
}

for 보다 forEach가 더 느리기 때문에 실행시간도 당연히 더 느려진다.

테스트 1 〉	통과 (77.46ms, 16.6MB)
테스트 2 〉	통과 (84.20ms, 16.4MB)
테스트 3 〉	통과 (23.64ms, 16.2MB)
테스트 4 〉	통과 (14.08ms, 16.5MB)
테스트 5 〉	통과 (81.58ms, 16.4MB)
테스트 6 〉	통과 (1008.58ms, 16.4MB)
테스트 7 〉	통과 (24.58ms, 16.3MB)
테스트 8 〉	통과 (2069.57ms, 16.6MB)
테스트 9 〉	통과 (150.36ms, 16.5MB)
테스트 10 〉	통과 (2399.58ms, 16.4MB)
테스트 11 〉	통과 (3.56ms, 16.4MB)
테스트 12 〉	통과 (1.46ms, 16.4MB)
테스트 13 〉	통과 (4.83ms, 16.4MB)
테스트 14 〉	통과 (1.53ms, 16.5MB)
테스트 15 〉	통과 (0.68ms, 16.5MB)
테스트 16 〉	통과 (6453.26ms, 16.2MB)
테스트 17 〉	통과 (8351.00ms, 16.3MB)
테스트 18 〉	통과 (48.33ms, 16.5MB)
테스트 19 〉	통과 (0.88ms, 16.4MB)
테스트 20 〉	통과 (8251.90ms, 16.5MB)
테스트 21 〉	통과 (7166.18ms, 16.4MB)
테스트 22 〉	통과 (1526.53ms, 16.5MB)
테스트 23 〉	통과 (0.07ms, 16.1MB)
테스트 24 〉	통과 (5985.34ms, 16.6MB)
테스트 25 〉	통과 (6182.21ms, 16.2MB)
테스트 26 〉	통과 (0.13ms, 16.4MB)

다른 사람 풀이

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
}

소수를 알 수 있으려면 무조건 반복문을 다 돌아야한다고 생각했는데 아니었다.

만약 중간에 나누어 지는 게 있다면 반복문을 빠져나가 false를 내보내면 된다.

다른 사람의 풀이에서 받아온 아이디어로 다시 코드를 짰다.

다른 사람의 풀이를 참고한 나의 풀이

import Foundation

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

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

테스트 1 〉	통과 (0.81ms, 16.4MB)
테스트 2 〉	통과 (1.08ms, 16.3MB)
테스트 3 〉	통과 (0.23ms, 16.2MB)
테스트 4 〉	통과 (0.16ms, 16.4MB)
테스트 5 〉	통과 (1.19ms, 16.2MB)
테스트 6 〉	통과 (13.09ms, 16.4MB)
테스트 7 〉	통과 (0.28ms, 16.3MB)
테스트 8 〉	통과 (16.21ms, 16.4MB)
테스트 9 〉	통과 (1.37ms, 16.3MB)
테스트 10 〉	통과 (15.44ms, 16.4MB)
테스트 11 〉	통과 (0.05ms, 16.3MB)
테스트 12 〉	통과 (0.04ms, 16.6MB)
테스트 13 〉	통과 (0.08ms, 16.3MB)
테스트 14 〉	통과 (0.03ms, 16.5MB)
테스트 15 〉	통과 (0.03ms, 16.5MB)
테스트 16 〉	통과 (48.69ms, 16.5MB)
테스트 17 〉	통과 (0.84ms, 16.4MB)
테스트 18 〉	통과 (0.80ms, 16.2MB)
테스트 19 〉	통과 (0.06ms, 16.4MB)
테스트 20 〉	통과 (98.30ms, 16.5MB)
테스트 21 〉	통과 (53.67ms, 16.5MB)
테스트 22 〉	통과 (0.35ms, 16.6MB)
테스트 23 〉	통과 (0.01ms, 16.3MB)
테스트 24 〉	통과 (47.29ms, 16.4MB)
테스트 25 〉	통과 (61.05ms, 16.5MB)
테스트 26 〉	통과 (0.02ms, 16.5MB)

역시나 시간을 훨~~씬 줄일 수 있었다.

중요한 개념

• 소수인지 아닌지를 판별할 때는 반복문을 처음부터 끝까지 돌리지 않고, 조건에 부합하지 않는다면 바로 빠져나오게 코드를 짜면 시간을 훨씬 줄일 수 있다.