BOJ 5568번 카드 놓기

BOJ 5568번 카드 놓기

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.

출력

첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.

핵심은, 중복 정수를 Set으로 없애주면 된다.

단, 유의할 점은 permutations의 결과값 (ex. [(‘1’, ‘2’), (‘1’, ‘12’), (‘1’, ‘1’), (‘2’, ‘1’)…]와 같은 형태)을 set에 넣어서 중복값을 없애고 끝내면 안된다.

이 집합값들을 붙여서 정수로 만들면 (ex. [12,112,11,21 …]) 여기서 예상치 못한 중복값이 생길 수 있다는 것이다.

그래서 permutations을 만든 이후에, 각 조합을 join으로 붙여서 정수 형태 (실제로 int는 아님, join은 str에만 쓸 수 있기 때문에)이를 set으로 만든 길이를 출력해야 한다.

from itertools import permutations
n = int(input())
k = int(input())
s = []

for _ in range(n):
    s.append(input())

permute = list(permutations(s,k))
result = []

for i in permute:
    result.append("".join(list(i)))

print(len(set(result)))