문제
상근이는 카드 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개 줄에는 카드에 적혀있는 수가 주어진다.
출력
첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.
예제 입력 1
4
2
1
2
12
1
예제 출력 1
7
예제 입력 2
6
3
72
2
12
7
2
1
예제 출력 2
68
문제 해결 과정
이 문제는 이중 포문이나 while문을 통해 풀면 시간 문제를 해결할 수 없을 것이라고 생각했다.
그래서 문득 떠오른게 조합과 순열과 관련된 라이브러리였다.
파이썬 내부에는 조합과 순열을 만드는 라이브러리가 존재한다.
순열을 통해 중복되는 것을 제거하면 개수를 쉽게 셀 수 있을 것이라고 생각했다.
처음에는 다음과 같이 짰다.
from itertools import permutations
n = int(input())
k = int(input())
num_list = []
for _ in range(n) :
num = int(input())
num_list.append(num)
combi = set(permutations(num_list, k))
print(len(combi))오답이라고 떴는데, 생각해보니 [72, 2, 1] 이나 [7, 22, 1]은 문자열로 만들었을 때 7221로 같은 문자열이라서 문제 조건을 생각하면 중복 처리가 되어야하는데 저렇게 만들면 당연히 같은 수열이 아니기에 set 자료 구조에는 다른 것을 담긴다.
그러면 저 중간에 공백을 지워야하는데 그 때 join이라는 함수를 사용한다.
join은 구분자를 정해서 구분 되어있는 문자열을 하나로 합치는 것이다.
그래서 바로 다음과 같이 코드를 수정했다.
import itertools
n = int(input())
k = int(input())
num_list = []
for _ in range(n) :
num = int(input())
num_list.append(num)
print(len(set("".join(i) for i in itertools.permutations(num_list, k))))다음과 같이 하니 또 Type Error가 떴다.
join은 앞서 말했듯 문자열을 하나로 합치는 것인데 나는 num에다가 정수로 입력을 했기 때문에 Type Error가 떴던 것이다. join 함수에 들어갈 매개 변수의 Type이 문자열이어야한다.
그래서 입력을 할 때 그냥 문자열로 입력이 되도록 했다.
최종 코드
import itertools
n = int(input())
k = int(input())
num_list = []
for _ in range(n) :
num = input()
num_list.append(num)
print(len(set("".join(i) for i in itertools.permutations(num_list, k))))