[프로그래머스 lv2]소수 찾기

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

프로그래머스

 

문제설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

 

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

 

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.

numbers는 0~9까지 숫자만으로 이루어져 있습니다.

"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers return

"17"      3

"011"    2

입출력 예 설명

예제 #1

[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

 

예제 #2

[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

 

11과 011은 같은 숫자로 취급합니다.

문제 해결 방법

1. numbers 문자열을 문자로 떼내어 리스트에 정리한다. 

2. 정리한 리스트를 permutations함수를 통해 각 원소들을 통해 만들 수 있는 조합 모든 경우(한자리, 두자리, 세자리 ,, numbers의 길이만큼의 자리)를 리스트에 정리한다. 

3. 소수판별 함수를 만들어서 위의 리스트 원소들을 대상으로 소수 판별을 한다. 

4. 결과 출력

코드 구현

from itertools import permutations

def solution(numbers):
    answer = 0
    numbers= str(numbers)
    Nlist=[]
    
    for i in range(len(numbers)):
        Nlist.append(str(numbers[i]))
        
    totalList = []
    for i in range(len(numbers)):
        if i == len(numbers):
            break
        totalList += list(map(''.join, (permutations(Nlist, i+1))))
    
    totalList=list(map(int, totalList))
    totalList=set(totalList)
    totalList=list(totalList)
    
    if 0 in totalList:
        totalList.remove(0)
    
    if 1 in totalList:
        totalList.remove(1)
    
    
    def primenumber(x):
        # 2부터 x-1까지 순회
        for i in range(2, x):
            if x % i == 0:
                # 하나라도 나눠 떨어지면 False 반환
                return False
        # 아무것도 나눠 떨어지는게 없으면 True 반환
        return True
    
    for i in range(len(totalList)):
        if primenumber(totalList[i])== True:
            answer+=1
            
    
# 어둠의 잔해 소수 판별기 
    
#     topic=2
#     check=0

#     for i in range(len(totalList)):
#         while 1:
#             if totalList[i] == 0:
#                 # 원소 0은 pass
#                 pass
            
#             if totalList[i] % topic == 0:
#                 check+=1
#                 if check ==1:
#                     break
#                 topic+=1   
#             else:
#                 topic+=1
            
#             if topic == totalList[i]:
#                 topic = 2
#                 break
                
#         if check == 1:
#             answer+=1
#             check=0
#         else:
#             check=0
#             pass
        

    
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

하지않음 

어려웠던 점

문제를 어떻게 풀어야하겠다는 것은 알겠지만서도, 자잘한 문법, 함수 사용법을 정확하게 몰라서 좀 시간이 걸렸다. 

생각하는데로 출력하고 활용하는것이 좀 어려웠다. 

 

특히 튜플 자료형, join함수, map함수, map객체, set함수 등에 대해서 잘 몰라서 새로 찾아봤다. 

 

소수를 찾는 로직도 예전에 문제를 한번 풀어봤었는 경험으로 코드를 짜봤는데(어둠의 잔해 소수 판별기), 시간초과가 나왔다. 왜그럴까??? 빈틈없이 짰다고 생각했는데, 시간날때 다시 한번 봐야겠다.