소수 만들기 / 프로그래머스, 파이썬 코딩테스트 연습 Summer/Winter Coding(~2018)

문제

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

 

 

제출답안

def solution(nums):
    answer = 0
    result = dict()  # 세 수의 합과 카운트를 담을 딕셔너리
    # 주어진 배열의 경우의 수 구하기
    for i, n1 in enumerate(nums):
        for j, n2 in enumerate(nums[i+1:]):
            for n3 in nums[i+1:][j+1:]:
                sum_nums = n1+n2+n3  # 세 수의 합
                # 1이상 자연수 3개를 합할 경우 무조건 2 이상.
                # 2이상 짝수에는 소수가 없다. 짝수합은 제외하여 경우의 수 줄이기
                if sum_nums % 2: # 합이 짝수가 아닌 경우
                    if sum_nums in result: # 홀수인 합이 딕셔너리에 있을경우
                        result[sum_nums] += 1 # 카운트 1 추가
                    else:# 홀수인 합이 딕셔너리에 없을 경우
                        result[sum_nums] = 1 # 카운트 1로 설정

    set_nums = set(result.keys()) #딕셔너리 내 key, 소수들의 집합 생성
    max_num = max(set_nums)# 가장 큰 소수

    # 에라토스테네스의 체 홀수버전
    for i in range(3, max_num+1, 2):  # range: 3 이상 result 최대값 이하의 모든 홀수
        multiple = set(range(i*2,max_num + 1, i))  # 각 홀수의 배수 집합
        set_nums -= multiple  # result와 배수집합의 차집합 >> 결과적으로 배수가 없는 값 즉 소수만 남음

    # 각 소수의 카운트 횟수 더하기. 즉 경우의 수
    for prime_sum in set_nums:
        answer+=result[prime_sum]
    return answer

 

 

이전에 풀었던
소수찾기에서 배운 소수탐지 알고리즘 사용
두 개 뽑아서 더하기에서 배운 조합 알고리즘 사용


하지만 지속적으로 런타임 에러 발생

개선답안

 

세 자연수의 합을 담는 딕셔너리 result가 비어있거나
홀수 합을 담은 집합 set_nums가 비어있을 경우 
런타임 에러가 발생

따라서 result 또는 set_nums가 비었을 경우
answer을 0으로 리턴하도록 처리함

def solution(nums):
    answer = 0
    result = dict()  # 세 수의 합과 카운트를 담을 딕셔너리
    # 주어진 배열의 경우의 수 구하기
    for i, n1 in enumerate(nums):
        for j, n2 in enumerate(nums[i+1:]):
            for n3 in nums[i+1:][j+1:]:
                sum_nums = n1+n2+n3  # 세 수의 합
                # 1이상 자연수 3개를 합할 경우 무조건 2 이상.
                # 2이상 짝수에는 소수가 없다. 짝수합은 제외하여 경우의 수 줄이기
                if sum_nums % 2: # 합이 짝수가 아닌 경우
                    if sum_nums in result: # 홀수인 합이 딕셔너리에 있을경우
                        result[sum_nums] += 1 # 카운트 1 추가
                    else:# 홀수인 합이 딕셔너리에 없을 경우
                        result[sum_nums] = 1 # 카운트 1로 설정
    if len(result):
        set_nums = set(result.keys()) #딕셔너리 내 key, 소수들의 집합 생성
        max_num = max(set_nums)# 가장 큰 홀수

        # 에라토스테네스의 체 홀수버전
        for i in range(3, max_num+1, 2):  # range: 3 이상 result 최대값 이하의 모든 홀수
            multiple = set(range(i*2,max_num + 1, i))  # 각 홀수의 배수 집합
            set_nums -= set(range(i*2, max_num+1, i))  # result와 배수집합의 차집합 >> 결과적으로 배수가 없는 값 즉 소수만 남음
            if set_nums == {*()}: 
                break # set_nums 
    
        if set_nums != {*()}: 
        # 각 소수의 카운트 횟수 더하기. 즉 경우의 수
            for prime_sum in set_nums:
                answer+=result[prime_sum]
    
    return answer

 

개선 전수 성능 비교

획득점수
3점

문제 바로가기