[백준] 3671번 산업 스파이의 편지

💡문제접근

• 간단한 소수 판정 문제라고 생각하고 무리없이 코드를 작성하고 제출했는데 25%에서 WA를 받았다.
• 코드에 어떤 문제가 있는지 보아하니 ①중복을 고려하지 않았고 ②숫자의 맨 앞자리가 0인 경우를 제대로 체크하지못했다. 중복을 제거하기 위해서 set을 이용해 중복을 제거해주었고 종이 조각에 적혀있는 숫자의 맨 앞자리가 0인 경우 continue문을 실행시켜주었다.

💡코드(메모리 : 113044KB, 시간 : 2608ms)

from itertools import permutations
import math
import sys
input = sys.stdin.readline

num = 9999999
prime_number = [True] * (num + 1)
prime_number[0] = False
prime_number[1] = False
for i in range(2, int(math.sqrt(num)) + 1):
    if prime_number[i]:
        for j in range(i*i, num+1, i):
            prime_number[j] = False

T = int(input())
for _ in range(T):
    cnt = 0
    number = input().strip()
    lenNumber = len(number)
    li = []
    for i in range(lenNumber):
        li.append(int(number[i]))
    for i in range(1, lenNumber+1):
        for j in list(set(permutations(li, i))):
            temp = ''.join(map(str, j))
            if temp[0] == "0":
                continue
            else:
                if prime_number[int(temp)]:
                    cnt += 1
    print(cnt)

💡소요시간 : 51m