티스토리 뷰

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

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

이 문제는 '순열'을 구하는 알고리즘을 응용해 풀어야 합니다. 예를들면 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 연산을 이용해 소수인지 판별 할 수 있습니다.

 

728x90
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/10   »
1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31
글 보관함