[프로그래머스] LV1 / 소수만들기/ 파이썬

💻 문제

프로그래머스 Lv1. 소수만들기 문제이다.

---

💡 내 코드

def isPrime(sum):
    for i in range(2,sum):
        if sum % i == 0:
            return False
    return True 
    
def solution(nums):
    answer,sum = 0,0

    for i in range(0,len(nums)-2):
        for k in range (i+1, len(nums)-1):
            for j in range (k+1, len(nums)):
                sum = nums[i]+nums[k]+nums[j]
                if isPrime(sum) : answer+=1

    return answer

📚 해결 과정

배열에 들어있는 숫자들 중 세 개를 선택하여 소수가 되는 경우의 수를 판별해야했기에 3중 for문으로 숫자를 선택하는 코드를 작성하고 소수인지 아닌지 판별하는 함수를 통해 문제를 풀었다.

---

💡 개선 코드

삼중 for문을 사용하기도 했고 코드에 개선할 부분이 많아 보여 다른 분들의 코드를 참고하여 보완점을 찾았다.

1. 소수 판별 코드

def isPrime(sum):
    for i in range(2,sum):
        if sum % i == 0:
            return False
    return True

기존 코드에서는 for문을 소수인지 판별하고자 하는 수 전체를 돌도록 작성하였는데 이렇게 하게 되면 시간 복잡도가 증가하게된다.

이때 가운데 약수를 기준으로 수들은 대칭적인 구조를 보인다.
다시 말해, 16의 경우 약수로 1,2,4,6,16 을 가지게 되는데

• 1 X 16 = 16
• 2 X 8 = 16
• 4 X 4 = 16
• 8 X 2 = 16
• 16 X 1 = 16

위와 같이 4x4 즉 제곱근을 기준으로 대칭적인 구조를 가지는 것을 확인할 수 있다. 그렇기 때문에 for문이 숫자 범위를 전부 도는 것이 아닌 제곱근까지 돌게 해도 소수를 판별할 수 있다.

아래와 같이 개선된 코드를 작성할 수 있다.

def isPrime(result):
    for i in range(2,(result//2)+1):
        if result % i == 0:
            return False
    return True

• (sum//2)+1 대신 math.sqrt(sum)) + 1 을 사용할 수도 있다.

2. 3중 for문 대신 파이썬 내장함수 활용

3중 for문을 사용하게 되면 시간 복잡도 측면에서 안 좋기도 하고 파이썬은 내장 함수가 아주 잘 되어있는 편이다. 물론 나는 아직 익숙치 않아 써먹지 못하고 있지만 ..

그 중 combination()이라는 함수를 활용하면 중복없이 조합을 반환해준다.

특정 배열 내에서 일정 수 만큼의 조합을 생성하고 싶다면 combination(list,num) 에서 list 에는 배열 변수를, num에는 원하는 조합의 개수를 넣어주면 된다.

from itertools import combinations

def isPrime(result):
    for i in range(2,(result//2)+1):
        if result % i == 0:
            return False
    return True 

def solution(nums):
    answer=0

    comb = list(combinations(nums,3))
    for i in comb:
        if isPrime(sum(i)) : answer+=1
    return answer

---

파이썬 내장 함수들에 대해서 공부해야겠다