[완전탐색] 프로그래머스 lv2. 소수찾기 (feat. 순열 조합, extend, permutations)

문제

종이 조각의 숫자들을 문자열 numbers로 받는다고 할 때, 각 문자열로 만들 수 있는 숫자 중 소수가 몇개인지 반환하라.

내 코드 플로우

1. 문자열로 만들 수 있는 모든 길이의 조합을 리스트로 만든다.
2. '01' 이나 '1'은 같은 숫자를 의미하기 때문에, 중복되는 값들은 조합 리스트에 넣지 않도록한다.
3. 조합 숫자 리스트 전체를 돌며, 나누어 떨어지는 약수를 가지고 있는지 확인한다.
4. 가지고 있지 않다면, cnt 값을 +1 해준다.

전체 코드

from itertools import permutations
def solution(numbers):

    cnt = 0
    tot = []
    for i in range(1, len(numbers)+1):
        arr =  list(int(i) for i in list(map(''.join, permutations(numbers,i))))
        tot.extend(a for a in arr if a not in tot)

    for n in tot:
        sosu = True
        if n == 1 or n == 0:
            continue
        for m in range(2,n):
            if n%m == 0:
                # 소수아님, 약수가 있다는 뜻
                sosu = False
                break
        if sosu:
            cnt += 1
            print(n)

    return cnt

permutations 순열

list나 str을 특정길이의 조합으로 반환해주는 메서드이다. import 방식에 따라 사용하는 양식이 달라진다는 점 유의하자.

 

1. import itertools

import itertools ... itertools.permutations(arr, long)

2. from itertools import permutations

from itertools import permutations ... permutations(arr, long)

permutations(arr) 만으로도 기능하는데, 문제에서 모든 자리수의 숫자로 조합해야하기 때문에 길이별(1~문자열길이)로 조합을 별도로 받아서 전체 조합 리스트를 만들었다. 

 

permatuations 활용

기본형

lst = [1,2,3]
arr = list(permutations(lst))
>>> [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]

permatuations 응용과 길이 지정 파라미터가 필수인 combinations

numbers = '123'
arr = list(int(i) for i in list(map(''.join, permutations(numbers))))
>>> [123, 132, 213, 231, 312, 321]
# 최대 길이의 순열 조합을 반환함


com_arr_e = lst2 = list(int(i) for i in list(map(''.join, combinations(lst))))
>>> TypeErrorL: combinations() missing required argument 'r'
# combinations는 자리수 있어야 함

com_arr = list(int(i) for i in list(map(''.join, combinations(lst,3))))
>>> [123]

 

combinations

permutations와 사용이 거의 똑같다. 순서가 반영된 permutations와 달리 반환값에 순서를 고려하지 않은 조합 리스트가 반환된다.
from itertools import combinations

list(combinations(arr, 2))

 

한 줄 표현식

list(int(i) for i in list(map(''.join, permutations(numbers,i))))

==

[(int(i) for i in list(map(''.join, permutations(numbers,i)))]

문자형태인 숫자들을 하나씩 꺼내서 붙여서 새로운 숫자 조합으로 만들 것이기 때문에 ( 1,1 => 11 ) ''.join 을 원소마다 해주도록 map을 쓰고, 이를 새로운 list로 만들었다. 내부에 생성된 list들을 다시 int요소인 배열로 만들어 주기 위해 **[ int(x) for x in arr ]** 를 추가해주었다.

남은 의문점

extend 쓰면, 중복값 자동으로 제거되어 연장되는 게 아닌가? 왜 tot.extend(arr)하면 중복이 들어갈까?
그래서 굳이 if a not in tot 조건을 추가해줘야 했다.

 

---

++ 추가

날렸다가 다시 쓰는...

다른 분 코드를 참고하니, 중복이 없는 자료구조인 set의 활용과 set의 요소 제거, 약수를 찾기 위한 방법에서 참고할 부분이 있어 추가해본다. 나도 set을 썼었는데, 이 코드와 차이점은 a=set()을 미리 선언하고 |= 라는 연산자를 활용했다는 점이 달랐다. 나의 경우 위의 코드에서 list로만 바꿔서 썼었는데 뜻대로 잘 되지 않았었다. 

|= 연산자는 merge & update 연산자란다.(참고블로그)

a = set()
for i in range(len(n)):
    a |= set(map(int, map("".join, permutations(list(n), i + 1))))

for 문을 돌며 0과 1을 예외처리한 내 코드와 달리, set 배열에서 -= set(0,1)로 원소를 바로 삭제해줄 수 있다는 게 신기했다. 이렇게도 작동하는 구나. 약수를 구하는 for문에서는, 에라토스테네스의 체(위키피디아 이동)라는 걸 썼다고 한다. 2부터 돌면서 한놈 한놈의 배수들을 제거하는 건데, 예를 들어, 2, 4, 6, ... 마지막 숫자. 3, 6, 9, 12, ... , 마지막 숫자. 들을 a배열에서 제거하는 방법이다. 다만, 마지막 숫자는 배열의 가장 큰 숫자의 제곱근으로 되어 있는데, 약수는 짝을 이뤄서 곱셈으로 수를 표현하는 특징이 있기 때문에 범위를 반만 돌면 되기 때문인 것 같다. 10 = 2*5, 1*10 . 이런 식으로 짝을 이루기 때문에 작은 쪽(1,2)만 탐색해도, 약수가 있는지 아닌지 알 수 있는 것이다. 그 기준점이  1/2제곱인 제곱근이 된다는 건 생각 못했지만..! 

# 나머지 코드
a -= set(range(0, 2))
for i in range(2, int(max(a) ** 0.5) + 1):
    a -= set(range(i * 2, max(a) + 1, i))
return len(a)

 

** list 는 -= list(0,1) 이 작동하지 않는다. set만 가능