[프로그래머스]소수찾기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42839

프로그래머스

문제를 간단하게 요약하자면 다음과 같다.

숫자로 이루어진 문자열 numbers가 주어지는데, 이 수를 이용하여 만들 수 있는 소수는 몇 개인지 반환하는 것이다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. 먼저 소수인지를 판단하는 issosu함수를 작성한다.

2. 문자열을 이용하여 모든 경우의 수를 만들어야하기 때문에 DFS함수를 작성한다.

3. 소수면 numlist에 append 해주고 배열의 길이가 곧 소수의 갯수이므로 이를 반환해준다.

def issosu(number): #1번 : sqrt를 사용하여 시간복잡도를 줄일 수도 있지만
    if int(number)==0 or int(number)==1: #필자는 하나라도 나누어 떨어지면 False 반환하게 했다.
        return False
    for i in range(2,int(number)):
        if int(number)%i==0:
            return False
    return True

def dfs(new, i, numlist,check): #2번
    for j in new: #재귀를 실행했을 때
        num=i+j #문자열이기 때문에 +를 사용하여 1+1=2가 아닌 1+1=11로 합칠 수 있다.
        newnew=new.replace(j,'',1) #해당 문자를 한 번만 지워서 새로운 배열을 만들어준다.
        if int(num) not in check and issosu(num):
            numlist.append(num)
            check.append(int(num))
        if newnew: #해당 문자를 한 번만 지운 새로운 배열이 존재한다면 아직 순회가 덜 되었기 때문에, 다시 재귀 호출을 해준다.
            dfs(newnew,num,numlist,check)

def solution(numbers):
    answer = 0
    numlist=[] #소수를 담는 리스트이다. (문자열)
    check=[] #중복 여부를 판단하는 리스트이다. (int형)
                    #굳이 두 개로 나누어서 만든 이유는 문자열과 int형의 변환을 여러번 하는 것은 비효율적이라고 생각했기 때문이다.
    for i in numbers:
        if int(i) not in check and issosu(i): #중복되지 않고 소수이면 각 배열에 넣어준다.
            numlist.append(i)
            check.append(int(i)) #numbers가 문자열이기 때문에 check에는 int로 형변환을 한 뒤에 넣어준다.
        new=numbers.replace(i,'',1) #DFS 재귀를 사용하기 위한 코드이다.
                                                        #해당 문자를 한 번만 지운 새로운 numbers 배열이라고 봐도 무방하다
        dfs(new, i, numlist,check) #새로운 numbers 배열을 이용하여 재귀를 실행해준다.
    answer=len(numlist) #3번
    return answer

본 문제의 가장 큰 핵심은 모든 경우의 수의 문자열을 만드는 것이었다.

다른 블로그를 참고하니 permutations를 사용하여 모든 경우의 수를 만드는 풀이도 있었지만, 필자는 알고리즘 학습을 위해서 본 문제를 DFS를 사용하여 작성하였다.

기존의 배열에서 문자를 하나하나 지워가고 결합시키고 또 지우는 과정을 재귀호출로 반복하면서 모든 경우의 수를 만들 수 있었다.