[Python] Lv1.소수 만들기

https://programmers.co.kr/learn/courses/30/lessons/12977

코딩테스트 연습 - 소수 만들기

 

 

 

 

 

문제 설명

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

 

제한사항

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

 

나의 접근 방법 및 풀이

이번 문제는 크게 두 부분을 나누어서 생각했다.

첫 번째, 리스트에서 3개의 합을 조합하는 부분, 두 번째, 그 합들 중 소수를 판별하여 개수를 카운트하는 부분

(1) 세 수의 합

처음에는 전체 합에서 하나씩 빼면 되지 않을까 생각해 sum(nums)-(리스트 내 숫자)로 진행했지만, 실패였고 다시 생각해보니 조합만 생각하더라도 5C3이면 10개의 조합이 나와야 하는데, 내 방식대로 하면 리스트 길이만큼의 합만 나오는 것이었다.

개인적으로 파이썬의 itertools 라이브러리를 사용해서 풀고 싶지 않아서, 어떻게 세 수를 조합할까 생각하다 예전에 백준의 블랙잭 문제에서 같은 방식으로 풀이했던 기억이 떨올라 삼중 for() 문을 이용하였다.(아마 완전탐색 유형이었던 것 같다..?)

nSum = []
    ## 리스트에서 3개의 합 구하기(조합)
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                nSum.append(nums[i]+nums[j]+nums[k])

 (2) 소수 판별하여 카운트 하기

처음에는 나머지가 0이면 break를, 그 외의 경우에는 1씩 증가했는데 소수가 아닌 경우는 괜찮더라도 7처럼 소수는 for() 범위 안의 수들이 계속 카운트될 가능성이 있었다.

그래서 범위를 n+1까지로 재설정하고 나머지가 0일경우도 1씩 증가해서 최종적으로 판별할 때는 증가된 수가 1인 경우만 소수이기 때문에(자기 자신) 해당 경우만 카운트했다. 

## 소수 개수
    for n in nSum:
        cnt = 0
        for p in range(2, n+1):
            if n%p == 0:
                cnt += 1
        if cnt == 1:
            answer += 1

 <전체 코드>

def solution(nums):
    answer = 0
    nSum = []
    ## 리스트에서 3개의 합 구하기(조합)
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                nSum.append(nums[i]+nums[j]+nums[k])

    ## 소수 개수
    for n in nSum:
        cnt = 0
        for p in range(2, n+1):
            if n%p == 0:
                cnt += 1
        if cnt == 1:
            answer += 1

    return answer

 

다른 풀이

def solution(nums):
    from itertools import combinations as cb
    answer = 0
    for a in cb(nums, 3):
        cand = sum(a)
        for j in range(2, cand):
            if cand%j==0:
                break
        else:
            answer += 1
    return answer

다른 풀이에서는 3개의 조합을 구하는 부분에 itertools 라이브러리를 사용하였다.

그리고 소수를 판별하는 부분에서 내가 왜 안됐는지를 알 수 있었다. python의 for-else 관계를 체크를 안했었다.