[Python 파이썬] 프로그래머스 - 소수 찾기(Lv 2)

 

2024년 6월 22일

문제 링크 : 프로그래머스 - 소수 찾기(Lv 2)

---

문제 접근

 
해야하는 작업은 크게 2가지 이다.

1. 주어진 숫자 카드를 조합하여 나올 수 있는 모든 수를 구하기

2. 모든 수 중에서 소수 판별하기

 
 
1번 작업은 파이썬에서 itertools 라이브러리의 순열 함수 permutations()나 조합 함수 combinations()를 활용하면 쉽게 모든 수를 얻어낼 수 있지만, 나는 라이브러리의 힘을 최대한 빌리지 않기 위해 백트래킹 방식으로 구하였다.
0과 1, 그리고 2를 제외한 짝수는 모두 확실하게 소수가 아니기에 쓸데없는 연산을 줄이기 위하여, 조합을 진행하다 해당 수가 나왔다면 집합에 추가해주지 않았다.
 
이후, 2번 과정을 수행하기 위해 내가 구한 모든 수에 대해 " 2 ~ 현재 알고 싶은 수의 제곱근 "까지 모든 수의 배수인지 확인해주었다.
 
현재 알고 싶은 수의 제곱근까지의 배수만 확인하는 이유는 약수의 성질 때문이다.
 
16의 약수를 예로 들면 1, 2, 4, 8, 16 이다.
제곱근 값인 4를 기준으로 양 대칭 구조를 보이기 때문에, 약수의 성질을 이용해 largest // 2 까지의 배수가 아닌, 제곱근까지의 배수인지만 확인해주면 된다.
 
모든 수가 배수인지 아닌지를 확인하여, 최종 소수의 개수를 출력해주면 된다.

---

전체 코드

 

def back_tracking(now, used, used_cnt, length):
    global combi_nums
    global arr
    # 조합 가능한 수 추가
    if now != "" and now not in combi_nums:
        # 2는 소수임
        if int(now) == 2:
            combi_nums.add(int(now))
        # 짝수이거나 1이면 애초에 넣지 않음
        elif int(now) % 2 != 0 and now != "1":
            combi_nums.add(int(now))
    if length == used_cnt:
        return
    
    for idx in range(length):
        if not used[idx]:
            used[idx] = True
            if now == "" and arr[idx] == "0":
                back_tracking("", used, used_cnt + 1, length)
            else:
                back_tracking(now + arr[idx], used, used_cnt + 1, length)
            used[idx] = False

def solution(numbers):
    global combi_nums
    global arr

    arr = list(numbers)
    length = len(arr)

    # 조합 가능한 모든 수
    combi_nums = set()
    for i in range(length):
        used = [False] * length
        used[i] = True
        used_cnt = 1
        if arr[i] != "0":
            back_tracking(arr[i], used, used_cnt, length)
        # 수의 시작이 0인 경우
        else:
            back_tracking("", used, used_cnt, length)
    
    # answer 초기값 : 조합 가능 숫자의 개수
    answer = len(combi_nums)
    if answer == 0:
        return answer
    
    #소수 찾기
    nums = list(combi_nums)
    for num in nums:
        # 2는 소수임
        if num == 2:
            continue
        for n in range(2, int(num**0.5) + 1):
            # 소수가 아님을 확인
            if n != num:
                if num % n == 0:
                    answer -= 1
                    break
        
    return answer



if __name__ == "__main__":
    numbers = "9876543"
    print(solution(numbers))

---

풀이 후기

 
에라토스테네스의 체가 필요 없는 문제임에도 적용시켜보고자 시도했다가, 8번 케이스에서 시간초과를 당했었다.
O(NlglgN) 시간복잡도를 가지는 해당 알고리즘은 위 문제의 경우 N이 최대 9999999이므로 약 45,000,000번 연산해야 한다.

 

 
실제로 8번 케이스에서 N이 큰 값이도록 설정되어있어서인지, 에라토스테네스의 체를 활용하여 문제를 푸니 수행 시간이 지나치게 커지는 것을 알 수 있었다.
 
알고리즘을 적용했을 때 효율적인지 아닌지를 잘 생각해야겠다.