본문 바로가기

Algorithm

소수 만들기 / 프로그래머스

 

접근방법

특정 길이의 리스트에서 3가지의 수를 뽑는 모든 경우의 수 구하기

백트래킹

  1. 첫 번째 숫자를 고정하고,
  2. 두 번째 숫자를 첫 번째 숫자 이후의 값 중에서 선택,
  3. 세 번째 숫자를 두 번째 숫자 이후의 값 중에서 선택하여,
  4. 모든 경우의 수를 탐색하는 방식으로 구현

소수를 구할 때는 범위를 √n까지만 확인하면 된다!

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):  # √n까지만 확인
        if n % i == 0:
            return False
    return True

 

정답

import itertools
def solution(nums):
    answer = 0
    num = list(itertools.combinations(nums, 3))
    for i in num:
        isPrime = 0
        k = sum(i)
        for j in range(2, k):
            if k % j == 0:
                isPrime = 1
                break
        if isPrime == 0:
            answer = answer + 1
    return answer

 

 

'Algorithm' 카테고리의 다른 글

기사단원의 무기 / 프로그래머스  (0) 2025.03.04
덧칠하기 / 프로그래머스  (0) 2025.03.03
모의고사 / 프로그래머스  (0) 2025.02.28
과일장수 / 프로그래머스  (0) 2025.02.27
카드 뭉치 / 프로그래머스  (0) 2025.02.24