[Python] Permutation & Combination (프로그래머스 소수찾기 문제)

코테 문제 중에 소수 찾기 문제를 풀던 중 나는 재귀를 사용해서 어찌어찌 풀었지만

# import math

# numList = []
# def isPrime(n):
#     if(n == 2 or n == 3):
#         return True
#     if(n == 1 or n % 2 == 0):
#         return False
#     for i in range(3, int(math.sqrt(n))+1, 2):
#         if(n % i == 0):
#             return False
#     return True

# def getNum(num, index, word):
#     newNum = word + num[index]
#     if (int(newNum) not in numList and int(newNum) != 0):
#         numList.append(int(newNum))
#     numCopy = [] + num #리스트의 값을 복사하는 과정
#     numCopy.pop(index)
#     for i in range(len(numCopy)):
#         getNum(numCopy, i, newNum)

# def solution(numbers):
#     num = []
#     primeList = []
#     for i in range(len(numbers)):
#         num.append(numbers[i])
#     for i in range(len(num)):
#         getNum(num, i, "")
#     for i in numList:
#         if(isPrime(i)):
#             primeList.append(i)
#     answer = len(primeList)
#     return answer
#위에 건 쪽팔려서 올릴까 말까 고민 많이 했는데 그냥 올림

import math
primeSet = set()
def isPrime(n):
    if (n == 2 or n == 3):
        return True
    if (n in [0, 1] or n % 2 == 0):
        return False
    for i in range(3, int(math.sqrt(n))+1, 2):
        if (n % i == 0):
            return False
    return True

def recursive(combination, others):
    if (combination != ""):
        if (isPrime(int(combination))):
            primeSet.add(int(combination))
    for i in range(len(others)):
        recursive(combination+others[i], others[:i] + others[i+1:])

def solution(numbers):
    num = list(numbers)
    recursive("", numbers)
    return len(primeSet)

다른 사람들의 풀이를 보니

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    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)

이렇게 permutations라는기능을 사용해서 아주아주아주아주아주 간결하게 표현했다

그리고 문자열에 list()를 취해주면 각 원소를 하나의 요소로 저장한다는 것도 이제 알았네..

 

암튼 permutation이 뭔지 한번 알아보자!

---

Permutation(순열)

말 그대로 원소들을 골라 일렬로 나열한 것이다. 일렬로 나열하는 것(순서가 있음)이기 때문에 a와 b가 있을때 'ab' 'ba'는 다른 것으로 취급한다.

이번 소수문제에서는 우선 숫자카드(0~1)들을 이용해 만들 수 있는 모든 수를 구해야했다. 그 다음에 소수인지 아닌지를 확인하는 절차가 필요했고.. 그래서 permutations()를 사용했다. 숫자를 뽑아서 일렬로 나열하는 거니까!

일단 permutations함수에 대해 알아보자

from itertools import permutations

permutations(이터레이팅이 가능한 값(list, range(), etc), 몇개를 뽑을건지)

permutations는 파이썬에서 기본적으로 제공해주는 기능으로 itertools에서 불러올 수 있다.

파라미터로는 list나 range()함수와 같이 값을 하나씩 뽑을 수 있는 값과 몇개를 뽑아서 조합을 만들건지에 대한 값을 받는다.

우선 permutations(range(3), 2)를 입력해보겠다(permutation 형태로 반환하기 때문에 list로 변환해주고 결과값을 확인해야함)

from itertools import permutations

print(list(permutations(range(3), 2)))

#[(0, 1), (0, 2), (1, 0), (1, 2), (2, 0), (2, 1)]

 그러면 0, 1, 2 중 두 개를 뽑아 나타낼 수 있는 조합들을 모두 표현할 수 있다. 

그래서 이걸 이용해서 소수문제를 풀 수 있다!

물론 이렇게 쓰면 숫자로 사용하기 힘들기 때문에 map("".join, 순열)을 해서 각 숫자를 문자열로 변환하고 또 map(int, 문자열)로 변환해 숫자로 변환해야 한다.

 

암튼 정말 간단하게 문제를 풀 수 있을 것 같다.

 

다음으로 Combination이다.

---

Combination(조합)

combination은 순열과 비슷하지만 다른 점은 순서를 상관하지 않는다는 점이다.

즉 (a, b)와 (b, a)를 동일한 것으로 본다.

combination도 파이썬 내장기능이고 itertools에서 가져올 수 있다

from itertools import combinations

print(list(combinations(range(3), 2)))

#[(0, 1), (0, 2), (1, 2)]

위와 같이 순서는 상관없이 나올 수 있는 경우를 출력해줬다. 

소수찾기 문제에서는 1와 0카드가 주어질 때 10과 01은 다른 숫자이기 때문에 Permutation을 사용해야한다. 

 

코테도 결국 수학 싸움이다...