백준 - 5568(카드 놓기, python)

https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

문제 풀이

• n개의 카드 중에서 k개를 선택하여 그 수를 나열해 만들 수 있는 수의 개수를 구하는 문제
• 재귀를 이용해 만들 수 있는 수를 만들고 set에 저장해 중복을 제거해주면 되겠다 판단함
• 다만 재귀를 구현하던 중 코드가 꼬여서 다른사람의 풀이를 보았음..구현력 이슈

정답 코드(1)

# n개 중에서 k개를 선택하여 만들 수 있는 정수의 개수

n = int(input())
k = int(input())
numbers = []
for _ in range(n):
    numbers.append(input())


answer = set()
def permutation(cnt, perm, visit):
    global numbers

    if cnt ==k:
        answer.add(''.join(perm))
        return
    for idx in range(n):
        if not visit[idx]:
            visit[idx] = 1
            permutation(cnt+1, perm+[numbers[idx]], visit)
            visit[idx] = 0

permutation(0, [], [0]*n)
print(len(answer))

정답 코드(2)

from itertools import permutations
n = int(input())
k = int(input())
numbers = []
for _ in range(n):
    numbers.append(input())


answer = set()

for i in permutations(numbers, k):
    answer.add(''.join(i))
print(len(answer))

첫번째 정답은 풀이법은 떠올렸으나 구현을 못했는데

두번째 코드에서 파이썬의 라이브러리를 활용해 간단한 방법이 있었다.

 

알아보니 itertools.permutations는 배열에서 원하는 개수만큼의 순열을 찾아주는 함수인 것 같다.

 

 

출처

https://eboong.tistory.com/333

[n5568] 카드 놓기 in python

 

회고

• 문제가 실버4니깐 쉽겠지? 하고 만만하게보다 당황한 문제....' '.join(배열)을 이용해 배열의 원소들을 문자열로 합치는 것마저도 떠올리지 못함
• permutation 함수를 몰랐던건 그럴 수 있다쳐도 재귀함수로 구현할 수 있는 문제를 구현 못한건 적잖이 당황했다...