๊ธ€ ์ž‘์„ฑ์ž: ํƒ์‹œ ์šด์ „์‚ฌ
๋ฐ˜์‘ํ˜•

๐Ÿ•ต๏ธโ€โ™€๏ธ ์†Œ์ˆ˜ ์ฐพ๊ธฐ ๋ฌธ์ œ ํ’€์–ด๋ณด๊ธฐ

๐Ÿ˜ƒ ๋‚˜์˜ ์ฝ”๋“œ

from itertools import permutations 

def solution(numbers):
    answer = set()
    maximum = 10000000
    prime_lst = [False, False] + [True] * maximum
    for idx, num in enumerate(prime_lst):
        if num:
            k = idx*2
            while k <= maximum:
                prime_lst[k] = False
                k += idx
    for i in range(1, len(numbers)+1):
        perm = permutations(list(numbers), i)
        for i in list(perm):
            num = int("".join(list(i)))
            if prime_lst[num]:
                answer.add(num)
    return len(answer)

์™„์ „ ํƒ์ƒ‰exhaustive search๋ฅผ ์ด์šฉํ•˜์—ฌ ํ‘ธ๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. ๋ฌธ์ œ๋Š” ๋‘ ๊ฐœ์˜ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ ์„œ ํ’€ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ํ•ด๋‹น ์ˆซ์ž๊ฐ€ ์†Œ์ˆ˜์ธ์ง€ ํŒ๋ณ„ํ•˜๋Š” ๋ฌธ์ œ์™€ ์ˆซ์ž๋กœ ๋œ ๋ฐฐ์—ด๋กœ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์ˆซ์ž๋ฅผ ์–ป๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.

๋ฌธ์ œ์˜ ์กฐ๊ฑด์ธ ์ˆซ์ž๊ฐ€ ์ตœ๋Œ€ 7์ž๋ฆฌ๋•Œ๋ฌธ์— ๋ฏธ๋ฆฌ 10^7์ดํ•˜์˜ ๋ชจ๋“  ์†Œ์ˆ˜๋ฅผ ์ฐพ๋Š” ๊ณผ์ •์„ ๋จผ์ € ์ง„ํ–‰ํ•ฉ๋‹ˆ๋‹ค. ์—ฌ๊ธฐ์„  2๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜๋Š” ์—ฐ์†๋œ ์ž์—ฐ์ˆ˜๋ฅผ ๋ฏธ๋ฆฌ ์จ ๋‘๊ณ , ์ฒ˜์Œ ๋‚˜ํƒ€๋‚˜๋Š” ์ˆ˜์˜ ๋ฐฐ์ˆ˜๋“ค์„ ๋ชจ๋‘ ์ง€์šฐ๋Š” ์‹์œผ๋กœ ์†Œ์ˆ˜๋ฅผ ๋‚จ๊ธฐ๋Š” ๋ฐฉ์‹์ธ ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด๋ฅผ ์ด์šฉํ•ฉ๋‹ˆ๋‹ค. ์ด ๋ฐฉ๋ฒ•์€ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” ๋ชจ๋“  ์ˆซ์ž๋ฅผ ์ฐพ์€ ๋’ค ๊ทธ ์ˆซ์ž๊ฐ€ ๊ฐ๊ฐ ์†Œ์ˆ˜์ธ ์ง€ ํ™•์ธํ•˜๋Š” ์‹์œผ๋กœ ํ‘ธ๋Š” ๋Œ€์‹ ์— ๋” ๋น ๋ฅธ ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค.

๋‹ค์Œ์€ ์ˆซ์ž๋กœ ๋œ ๋ฐฐ์—ด๋กœ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” ์ˆซ์ž๋ฅผ ๊ตฌํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค. Python์˜ ๋‚ด์žฅ ๋ชจ๋“ˆ์ธ itertools์˜ permutations๋ฅผ ์ด์šฉํ•ด์„œ ์ˆœ์—ด์„ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. permutation์˜ ์ธ์ž๋Š” list์™€ r๋กœ list์— ์žˆ๋Š” ๋ฐ์ดํ„ฐ๋ฅผ ์ˆœ์„œ๋ฅผ ์ƒ๊ฐํ•ด์„œ r๊ฐœ ๋ฝ‘๊ฒŒ ํ•ฉ๋‹ˆ๋‹ค. ์ด๋ฅผ ์ด์šฉํ•˜์—ฌ 1๊ฐœ๋ถ€ํ„ฐ numbers์˜ ํฌ๊ธฐ๊นŒ์ง€ permutations๋ฅผ ์ด์šฉํ•ด์„œ ์ƒˆ๋กœ์šด ์ˆซ์ž ์กฐํ•ฉ์„ ๋งŒ๋“ญ๋‹ˆ๋‹ค. permutation์˜ ๊ฒฐ๊ณผ๊ฐ’์ธ tuple์„ list๋กœ ๋ฐ”๊พธ๊ณ  join์„ ์ด์šฉํ•ด์„œ string์œผ๋กœ ๋งŒ๋“ค๊ณ  ์ตœ์ข…์ ์œผ๋กœ int๋ฅผ ์ด์šฉํ•ด ์ •์ˆ˜๋กœ ๋งŒ๋“ค์–ด์ค๋‹ˆ๋‹ค.

์ด์ œ ์ด ์ •์ˆ˜๊ฐ’์„ ๋ฏธ๋ฆฌ ์ œ์ž‘ํ•ด๋†“์€ ์†Œ์ˆ˜๋ฅผ ํŒ๋ณ„ํ•˜๋Š” ๋ฐฐ์—ด์ธ prime_lst์— ๋„ฃ์–ด ์†Œ์ˆ˜ ์—ฌ๋ถ€๋ฅผ ํŒŒ์•…ํ•˜๊ณ  ์ค‘๋ณต์„ ๋ฐฉ์ง€ํ•˜๊ธฐ ์œ„ํ•ด set์— ๋„ฃ์–ด์ค๋‹ˆ๋‹ค. ๋งˆ์ง€๋ง‰์œผ๋กœ set์˜ ํฌ๊ธฐ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๋ฉด ๋ฌธ์ œ๊ฐ€ ๋งˆ๋ฌด๋ฆฌ๋ฉ๋‹ˆ๋‹ค.

๋ฐ˜์‘ํ˜•