[Programmers] 소수 찾기

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예
numbers return
17 3
011 2

입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.

나의 생각

두 가지 방법을 찾아야 한다는 생각이 들었다.

1. 소수 판별하는 코드를 구현해야 한다. 이 부분은 구글링의 도움을 받았다.

2. 순열을 구현해한다. "271" 이라는 문자열이 주어졌을 때, [ 2, 7, 1, 27, 21, 12, 17, 71, 72, 271, 217, 127, 172, 712, 721] 이 모든 경우를 다 판단해야 한다. 이 모든 경우를 구하는 코드를 어떻게 짤 것인지 생각해야 한다.

소수 판별

소수란?

2보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 수.

무식하게 for문을 돌려서 정의 그대로 구현하는 것은 어렵지 않지만, 시간 복잡도는 O(N) 이다. 우리가 판단해야 하는 소수는 한 가지가 아니라 경우에 따라서 몇 백만 가지가 될 것이기 때문에, 시간 초과가 될 것이라고 생각했다.

그래서 좀 더 효율적인 방법을 찾아보았고, 두 가지가 있었다.

1. 제곱근 까지 확인을 하는 방법

import math

def isPrime(x): # 제곱근까지만 보고 소수를 판별하는 함수
    global answer
    if x <= 1:
        return False
    for i in range(2, int(math.sqrt(x))+1): # 2부터 제곱근까지의 모든 수를 확인
        if x % i == 0:  # 소수가 아님
            return False
    answer += 1

시간복잡도는 O(N^(1/2)) 라고 할 수 있다. 매우 효율적이라고는 할 수 없으나, 후에 서술할 방법보다는 이 방법이 이번 문제에는 적합하다고 생각이 들었다.

2. 에라토스테네스의 체

이는 범위에 대한 소수 판별에 유리하다. 하는 방법은 다음과 같다.

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다.)
4. 더 이상 반복할 수 없을 때까지 2번과 3번의 과정을 반복한다.

# 소수 판별 함수(에라토스테네스의 체)
def is_prime_number(n):
    
    array = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화(0과 1은 제외)

    # 에라토스테네스의 체
    for i in range(2, int(math.sqrt(n)) + 1): 
        if array[i] == True: # i가 소수인 경우(남은 수인 경우)
            # i를 제외한 i의 모든 배수를 지우기
            j = 2
            while i * j <= n:
                array[i * j] = False
                j += 1

    return [ i for i in range(2, n+1) if array[i] ]

에라토스테네스의 체의 시간 복잡도는 O(Nlog(logN)) 으로 굉장히 빠르다. 하지만, N크기 만큼의 메모리를 저장하고 기억해야 하기 때문에, 7자리 자연수를 입력받는 이번 문제에서는 부적합하다고 생각하여 사용하지 않았다.

소수 판별 알고리즘 출처

순열 구현

어떻게 풀어야 할까 생각하다가, 예전에 백준에서 풀었던 N-Queen 문제가 생각이 났다. N-Queen 문제는 대표적인 백트래킹 문제인데, 그 때 배운 반복문 사용방법이 갑자기 생각나서 그와 비슷한 방식으로 재귀 함수를 사용해 보기로 했다.

import math

isused = []
nlist = []
usednum = []
answer = 0

def isPrime(x): # 제곱근까지만 보고 소수를 판별하는 함수
    global answer
    if x <= 1:
        return False
    for i in range(2, int(math.sqrt(x))+1): # 2부터 제곱근까지의 모든 수를 확인
        if x % i == 0:  # 소수가 아님
            return False
    answer += 1


def P(numbers, nlen, size):
    global isused
    global nlist
    global usednum
    for i in range(nlen):
        if len(nlist) < size <= nlen:  # size = 자리 수. 아직 자리수를 채우지 못했으면 추가해야징

            if not isused[i]:   # i번째 숫자가 사용 되었는지 확인한다. 중복되면 안되니까?
                nlist.append(numbers[i])
                isused[i] = True
                P(numbers, nlen, size + 1)
                isused[i] = False
        else:
            if len(nlist) >= 1:
                new_number = "".join(nlist)
                new_number = int(new_number)
                if not new_number in usednum:
                    usednum.append(new_number)
                    isPrime(int(new_number)) # 소수인지 판별
                nlist.pop()  # 자리수가 꽉 찼으면 소수인지 판별하고 팝 해야지요.


def solution(numbers):
    global isused
    global answer
    nlen = len(numbers) # 종이 조각의 개수.
    isused = [False] * nlen
    P(numbers,nlen,1)
    return answer

첫 번째 실행 결과

2, 9, 10, 11, 12 번 테스트 케이스를 통과하지 못했다. 왜 통과를 못했을까? 생각하여 코드 중간중간에 print문을 넣어서 확인을 해보니까, 내 코드가 모든 경우의 수를 탐색하지 않는다는 것을 알게 되었다. 왜 모든 경우의 수를 탐색하지 못한 걸까?

유심히 찾아보니, 조건문에 문제가 있었다. 리스트를 팝 하는 경우가 반복문에 들어가있어서, 팝을 하지 말아야 할 때도 팝을 해버렸다. 이걸 찾는데 30분이 걸리다니..

수정한 코드는 다음과 같다.

정답 코드

import math

isused = []
nlist = []
usednum = []
answer = 0

def isPrime(x): # 제곱근까지만 보고 소수를 판별하는 함수
    global answer
    if x <= 1:
        return False
    for i in range(2, int(math.sqrt(x))+1): # 2부터 제곱근까지의 모든 수를 확인
        if x % i == 0:  # 소수가 아님
            return False
    answer += 1


def P(numbers, nlen, size):
    global isused
    global nlist
    global usednum
    for i in range(nlen):
        if size <= nlen:  # size = 자리 수. 아직 자리수를 채우지 못했으면 추가해야징
            if not isused[i]:   # i번째 숫자가 사용 되었는지 확인한다. 중복되면 안되니까?
                nlist.append(numbers[i])
                isused[i] = True
                P(numbers, nlen, size + 1)
                isused[i] = False

    if len(nlist) >= 1:
        new_number = "".join(nlist)
        new_number = int(new_number)
        if not new_number in usednum:
            usednum.append(new_number)
            isPrime(int(new_number)) # 소수인지 판별
        nlist.pop()  # 자리수가 꽉 찼으면 소수인지 판별하고 팝 해야지요.


def solution(numbers):
    global isused
    global answer
    nlen = len(numbers) # 종이 조각의 개수.
    isused = [False] * nlen
    P(numbers,nlen,1)
    return answer

결과는 성공! 3시간이나 걸린 문제.. 끝!