[프로그래머스][완전탐색] 소수 찾기

programmers.co.kr/learn/courses/30/lessons/42839

코딩테스트 연습 - 소수 찾기

해설

내가 본래 c++이 주 언어여서 그런지 완전 c++ 스타일로 풀었다.

문제 해결은 간단하다

 

• permutation로직으로 모든 케이스를 생성하고 해당 케이스가 소수인지 아닌지 판별한다

 

 

여기서 permutation은 파이썬 내장 함수를 사용해도 되지만 기본적으로 어떻게 하는지 적어보면

for i in range(len(numbers)):
            if visit[i]:
                continue
            visit[i] = True
            newstring = string + numbers[i]
            dfs(newstring,cnt+1)
            visit[i] = False

이런 형태의 로직이 permutation이다.

 

 

• 이미 선택한 숫자면 for문에서 continue로 넘어간다.
• cnt번째 자리에 숫자를 선택했으면 True로 지정하고 cnt+1 로으로 넘어간다.
• 마지막에 False를 해주어 숫자 선택한걸 해제한다. 이러면 다음 포문에서 다른숫자를 선택 할 수 있다.

 

허나 이 문제는 숫자를 선택 안하는 경우도 있다. 예를들어 "17"이면 "1", "7" 이렇게 하나만 선택해주는 경우가 있다는 것이다.

 

그러므로 아래처럼 작성해주어야 한다.

 

for i in range(len(numbers)):
            if visit[i]:
                continue
            visit[i] = True
            dfs(string,cnt+1) # 선택안해주고 다음자리로 넘어감
            newstring = string + numbers[i]
            dfs(newstring,cnt+1) # 숫자 선택하고 다음으로 넘어감
            visit[i] = False

 

 

 

이런식으로 permutation을 하면 중복되는 숫자가 나온다. 이럴경우 set으로 처리해주자.

def solution(numbers):
    answer = 0
    visit = [False]*len(numbers)
    def check(num):
        if num < 2:
            return False
        for i in range(2,num):
            if num % i == 0:
                return False
        return True
    myset = set()
    def dfs(string, cnt):
        if cnt == len(numbers):
            if string == '':
                return
            if int(string) in myset:
                return
            if check(int(string)):
                myset.add(int(string))
                nonlocal answer
                answer+=1
                return
        for i in range(len(numbers)):
            if visit[i]:
                continue
            visit[i] = True
            dfs(string,cnt+1)
            newstring = string + numbers[i]
            dfs(newstring,cnt+1)
            visit[i] = False
    dfs('',0)
    
    return answer

 

 

내장 함수 permutations를 사용하면 아래처럼 더 간단하게 풀 수 있다.

from itertools import permutations
from functools import reduce
def check(num):
    if num < 2:
        return False
    for i in range(2,num):
        if num % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    myset = set()
    for i in range(1,len(numbers)+1):
        permutation = list(permutations(numbers,i))
        for num in permutation:
            number = int(reduce(lambda x,y : x+y,num))
            if number not in myset and check(number):
                myset.add(number)
                answer +=1
    return answer