You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

1 분 소요

1. 문제

[level 1] 소수 만들기 - 12977

문제 링크

성능 요약

메모리: 10.2 MB, 시간: 0.01 ms

구분

코딩테스트 연습 > Summer／Winter Coding（～2018）

채점결과


정확성: 100.0
합계: 100.0 / 100.0

문제 설명

주어진 숫자 중 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을 만들 수 있습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

2. 해결방법 시간복잡도

  1. 브루트 포스 O(N^3)
  2. 소수 판별 알고리즘 O(N^2)

3. 문제 해결 및 코드

  • 주석을 참고하면서 이해를 돕습니다.

4. 알고리즘 및 해설

  1. 위의 코드는 내가 처음 시도한 방법이다. 브루트 포스 말 그대로 무식하게 푼 방법이므로 참고만 하길 바란다.
  2. 문제는 3가지 숫자를 가지고 만들 수 있는 경우의 합을 가지고 소수일 경우 개수를 세서 출력한다.
  3. 매 반복문마다 이전 반복문과 겹치도록 계산한 방법이다.

5. 다시 해결한 방법

from itertools import combinations
import math
def solution(nums):
    tmp = [sum(list(i)) for i in list(combinations(nums, 3))]
    result = []
    for i in tmp:
        cnt = 0
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0:
                cnt = 1
                break
        if cnt == 0: result.append(i)
    return len(result)
  • 2가지 라이브러리를 사용하였다. math와 itertools의 combinations이다.
  • 문제에서 요구하는 경우의 수가 적을 경우 combinations를 통해 반복문 없이 낮은 시간복잡도로 간단하게 경우의 수를 구할 수 있다.
  • 이후 소수 판별 알고리즘방식으로 math.sqrt()를 사용해서 해당 수의 제곱근 + 1까지의 나누어지는 값이 없는 경우 소수로 판별하여 최종 결과 리스트에 넣었다.
    • 제곱근을 사용하는 이유는 소수가 아닌 경우 모두 짝을 이루는 수가 있으므로 반으로 줄여 메모리 누수를 최소화하는 방법이다.
  • 마지막으로 최종 리스트 길이를 출력한다.

참고