프로그래머스 level 1 - 소수찾기 (연습문제), level 2 - 소수찾기 (완전탐색) / 에라토스테네스의 체 이용

https://programmers.co.kr/learn/courses/30/lessons/12921

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

• set 자료형의 차집합 기능 이용하기
• 짝수는 소수가 될 수 없으니, 3부터 시작해서 2씩 커지게 한다.
• 단, 2도 소수이니 마지막에 정답+1을 리턴하도록 한다.

def solution(n):
    num = set([i for i in range(3, n+1, 2)])

    for i in range(3, n+1, 2):
        if i in num:
            num -= set([j for j in range(i*2, n+1, i)])
    return len(num) + 1

level2의 소수 찾기 문제도 다시 풀어보았다.

 

 

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

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

 

DFS로 열심히 풀다가 잘 안되서 itertools 라이브러리 썼다. 아직 어렵나보다 ^ㅠ

• "".join(list) => 리스트를 문자열화
• 근데 이게 더 시간 효율이 안좋은 것 같은데 굳이 이렇게 써야하나?

 

# 오답

def solution(numbers):
    def DFS(L, s):
        if L == len(numbers):
            if s != "":
                res.add(int(s))
            else:
                num2.add(s)
        else:
            for i in range(len(numbers)):
                if visited[i] == 0:
                    visited[i] = 1
                    DFS(L+1, s + num[i])
                    visited[i] = 0

    num = list(numbers) 
    res = set()
    visited = [0] * len(numbers)

    DFS(0, "")
    if "" in res:
        res.remove("")
    print(res)

    return 0

# 오답
import itertools as it

def solution(numbers):

    num = list(numbers) 
    res = set()
    
    for i in range(1, len(numbers)+1):
        for j in it.permutations(num, i):
            res.add(int("".join(j)))
            
    largest = max(list(res))
    res -= {0, 1, 2}
    for i in range(3, largest+1, 2):
        res -= set([j for j in range(i*2, largest+1, i)])
    return len(res)

 

import itertools as it

def is_prime(x):
    if x == 0:
        return False
    elif x == 1:
        return False
    else:
        for i in range(2, x):
            if x % i == 0:
                return False
    return True

def solution(numbers):

    num = list(numbers) 
    res = set()
    
    for i in range(1, len(numbers)+1):
        for j in it.permutations(num, i):
            res.add(int("".join(j)))
    
    cnt = 0
    for r in res:
        if is_prime(r):
            cnt += 1
            
    return cnt

 

DFS 로 푼 풀이

whwl.tistory.com/56