[완전탐색] 소수찾기

접근 방식

주어진 문자열을 중복없는 정수형 리스트로 변환 후 소수 판별하기

1. 문자열 -> 중복 없는 리스트화

from itertools import permutations

numbers = '011'

permuList = [] 
permuSet = [] 
for i in range(1, len(numbers)+1):
  tmp = list(permutations(numbers, i))
  for j in range(len(tmp)):
    if(len(tmp[j])==1):
      permuList.append(int(tmp[j][0]))
    else:
      sum = ''
      for k in range(len(tmp[j])):
        sum += tmp[j][k]
      permuList.append(int(sum))
  permuSet = list(set(permuList)) #중복 제거
  
print(permuList) #중복 고려 안한 original list
print(permuSet) #set을 이용해 중복 제거한 list

✏️ notes

• 순열(permutation) 활용 (itertools 라이브러리 permutations)

• 리스트 내에 있는 튜플 접근하는 게 어렵게 느껴짐.. 튜플도 똑같이 인덱스로 접근한다!! 다만 튜플 요소는 변경 불가능하니 주의..

• list의 중복을 제거하는 건 간단하다. list를 set으로 초기화 시켜주면 됨! (list->set->list와 같은 형식)

set1 = set(list1)
list2 = list(set1) #중복없는 리스트가 됨

2. 소수 판별하기

list1 = [0, 1, 101, 10, 11, 110]

for n in list1:
  flag = False
  if(n == 0 or n == 1): continue
  for i in range(2, n-1): #1과 자기자신 외의 수로 나누어지는지
    if(n % i == 0):
      flag = True
      break
  if(flag == True): continue 
  print(n)

최종 코드

from itertools import permutations

def solution(numbers):
#1. 문자열->중복없는 리스트화
    permuList = [] 
    permuSet = [] 
    for i in range(1, len(numbers)+1):
        tmp = list(permutations(numbers, i))
        for j in range(len(tmp)):
            if(len(tmp[j])==1):
                permuList.append(int(tmp[j][0]))
            else:
                sum = ''
                for k in range(len(tmp[j])):
                    sum += tmp[j][k]
                permuList.append(int(sum))
            permuSet = list(set(permuList)) #중복 제거
    
#2. 소수판별
    cnt = 0
    for n in permuSet:
        flag = False
        if(n == 0 or n == 1): continue
        for i in range(2, n-1): #1과 자기자신 외의 수로 나누어지는지
            if(n % i == 0):
                flag = True
                break
        if(flag == True): continue 
        cnt += 1
    
    return cnt

👀 파이썬-알못의 다른 풀이 염탐

⭐️ 튜플 문자열 붙이기 tip

''.join(map(str, 해당 리스트))

✅ join() 함수
String 사이에 특정 문자열을 삽입하여 나뉘어 있던 문자열을 합쳐주는 함수
✅ map() 함수
map(f, iterable)은 함수(f)와 반복가능한(iterable) 자료형을 입력받고, 입력받은 자료형의 각 요소를 함수(f)가 수행한 결과를 묶어서 반환하는 함수

이거 때문에 🐶고생했는데.. 이런 방식이 있었다고 한다..🥲
이렇게 갔으면 시간복잡도도 줄일 수 있었을 것.. 이걸 활용해서 다시 풀어보자

개선된 소스 코드

from itertools import permutations

def solution(numbers):
#1. 문자열->중복없는 리스트화 (변경)
    permuList = [] 
    permuSet = [] 
    for i in range(1, len(numbers)+1):
        tmp = list(permutations(numbers, i))
        for j in range(len(tmp)):
            num = int(''.join(map(str, tmp[j])))
            permuList.append(num)
    permuSet = list(set(permuList)) #중복 제거
    
#2. 소수판별
    cnt = 0
    for n in permuSet:
        flag = False
        if(n == 0 or n == 1): continue
        for i in range(2, n-1): #1과 자기자신 외의 수로 나누어지는지
            if(n % i == 0):
                flag = True
                break
        if(flag == True): continue 
        cnt += 1
    
    return cnt

📚 reference

1. 다른 풀이 방식 https://velog.io/@insutance/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4Python-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0

2. join(), map() 함수
   https://velog.io/@qhsh866/Python-split-join-map-%EB%AC%B8%EC%9E%90%EC%97%B4-%EA%B4%80%EB%A0%A8-%ED%95%A8%EC%88%98-%EC%A0%95%EB%A6%AC