n개의 카드를 한번씩 써서 만들 수 있는 숫자

프로그래머스 고득점킷 중 완전탐색에서 소수 문제를 풀 때 "n개의 카드를 이용해 만들 수 있는 숫자"를 구할 수 있어야 풀 수 있는 문제가 나옵니다.

https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3 

프로그래머스

 

이 문제는 '순열'을 구하는 알고리즘을 응용해 풀어야 합니다. 예를들면 0, 1, 1로 만들 수 있는 모든 숫자는 0, 1, 10, 11, 101, 110이 있습니다. 만들어진 숫자를 보면 일종의 '순열'입니다.

 

먼저 1, 2, 3을 이용해 구할 수 있는 모든 순열을 구해보겠습니다. 다음 코드는 주어진 배열에 있는 숫자를 이용해 순열을 구하는 코드 입니다.

def permutation(nums, current_nums):
    if len(current_nums) == len(nums):
        print(current_nums)

    for num in nums:
        if num not in current_nums:
            permutation(nums, current_nums + [num])


permutation([1, 2, 3], [])

결과

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

 

'순열'은 '순'서가 있는 나'열' 이라는 뜻으로 순서가 중요합니다. 조합은 순서는 고려하지 않기 때문에 [1, 2, 3], [2, 1, 3]이 같은 것으로 취급 하지만 순열은 위와 같이 1, 2, 3을 가지고 총 6개의 순열을 만들어 낼 수 있습니다.

 

위 문제에서는 예시로 0, 1, 1과 1, 7을 이용해 만들 수 있는 소수를 구하라고 합니다. 소수인지는 후에 판별 하면 되고 만들 수 있는 모든 숫자를 먼저 만들어야 합니다. 이 문제에서 해결하기 어려운 부분은 0, 1, 1이 각각 1개의 카드라는 것입니다. 순열을 구하는 알고리즘은 current_nums에 이미 들어있는 숫자를 제외하고 재귀호출을 하지만 0, 1, 1의 경우는 1이 두개이기 때문에 이 조건을 이용해 재귀를 구성하면 안됩니다.

 

해법은 다음과 같이 nums를 모두 반복하지만 1개씩 빼서 넣는 방법을 이용합니다. 탈출(escape)조건은 nums의 길이가 0이면 탈출하게 구성합니다.

def permutations(nums, current_nums, result_set):
    print(current_nums)
    con = ''.join(current_nums)
    if con != '':
        result_set.add(int(con))

    if len(nums) == 0:
        return
    for n in nums:
        nums.remove(n)
        permutations(nums, current_nums + [n], result_set)
        nums.append(n)

s1 = set()
permutations(["0", "1", "1"], [], s1)
print(s1)

결과

{0, 1, 101, 10, 11, 110}

 

재귀 호출을 통해 만들어진 순열 중 ''를 제외하고 int로 변환한 후 set에 넣으면 중복이 제거된 만들 수 있는 모든 숫자를 구할 수 있습니다.

 

소수인지를 판별하고 싶다면 에라토스테네스체 알고리즘을 이용해 소수들을 만들어 낸 뒤 in 연산을 이용해 소수인지 판별 할 수 있습니다.