99클럽 코테 스터디 23일차 TIL: Python Itertools

오늘의 문제 | 프로그래머스: 소수 찾기

우선 소수 관련 문제이므로 소수 체크하는 함수가 필요하다. 또한 순서 상관없이 문자열을 만들어야 하므로 이번에도 itertools를 이용해야 하지 않을까하는 생각이 든다.

아이디어: 길이 별로 permutations를 돌려서 모든 경우의 수를 만들어내자

하지만 이 아이디어의 치명적인 문제는, 모든 문자열 기준으로 돌릴 경우 이미 검사한 숫자도 나올 수 있다는 것이다. 그래서 visit 배열을 따로 선언하여 답으로 나오지 않은 숫자만 확인했다.

from itertools import permutations

def isPrime(number):
    if number<=1: return False
    for i in range(2,int(number**(1/2))+1):
        if number%i==0: return False
    return True

def solution(numbers):
    answer = 0
    visit=[True for i in range(1_000_000)]
    
    for i in range(1,len(numbers)+1):
        numList = permutations(numbers,i)
        for num in numList:
            numInt=int("".join(num))
            if isPrime(numInt) and visit[numInt]:
                answer+=1
                visit[numInt]=False
    return answer

오늘의 회고

오늘 문제도 초반에 약간 힘들었다. 어떻게 완전 탐색을 돌려야 시간 초과 안나면서 중복없이 확인할 수 있을까라는 아이디어를 떠올리는게 쉽지 않았다. 하지만 결국은 permutations을 써야 하는 문제였기에 큰 무리없이 해결할 수 있었다고 생각한다. 뭔가 itertools를 잘쓰는게 중요하다는 생각이 요새 들고 있다.