[프로그래머스] 소수 만들기 Go Code

2022.08.04 - [Coding Test/Python] - [프로그래머스] 소수 만들기 Python Code

저번 포스트에 이어 이번엔 Go로 풀어보겠다.

---

문제

 

3개를 뽑아야 하므로 3중 for문을 돌며 3개의 수를 뽑을 것이다.

 

그리고 이 수를 더한 후 소수인지 판별하고

 

소수라면 정답에 더하도록 할 것이다.

---

Code

import "math"

func solution(nums []int) int {
    answer := 0

    for n1 := 0; n1 < len(nums); n1++ {
        for n2 := n1 + 1; n2 < len(nums); n2++ {
            for n3 := n2 + 1; n3 < len(nums); n3++ {
                sum := nums[n1] + nums[n2] + nums[n3]
                flag := false
                for div := 2; div <= int(math.Sqrt(float64(sum))); div++ {
                    if sum%div == 0 {
                        flag = true
                        break
                    }
                }
                if !flag {
                    answer++
                }
            }
        }
    }

    return answer
}

원시적으로 3중 for문을 돌며 수를 뽑고

해당 수를 모두 더한 뒤 다시 for문을 돌며 소수인지 판별하도록 했다.

 

소수 판별할 때는 시간 효율성을 위해 이전 포스트와 같이 제곱근까지만 반복하도록 했다.

 

이런 류의 조합 문제는 어쩔 수 없이 시간 복잡도가 높을 수밖에 없다.

 

Go에서는 이게 최적의 방법이라고 생각한다.

(더 좋은 방법이 있다면 댓글이나 메일 부탁드립니다.)