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개 줄에는 카드에 적혀있는 수가 주어진다.

출력

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

---

예제

4
2
1
2
12
1
>> 7

---

풀이

def my_cards(drawIdx):
    if drawIdx == K:
        result.add("".join(drawList))
        return

    for idx in range(0, N):
        if visited[idx]:
            continue

        visited[idx] = True
        drawList[drawIdx] = c_list[idx]
        my_cards(drawIdx+1)
        visited[idx] = False

import sys
N = int(sys.stdin.readline())   
K = int(sys.stdin.readline())

visited = [False] * N
drawList = [0] * K
c_list = []
for _ in range(N):
    c_list.append(input())

result = set()
my_cards(0)
print(len(result))

1. visited = [False] * N → 뽑은 카드의 인덱스를 담아둘 리스트 (길이 N) : True/False
2. drawList = [0] * K → 뽑은 카드를 넣어둘 리스트 (길이 K) : 0
3. cardList = [] → 전체 카드를 넣어둘 리스트 : input 값
4. result = set() → 중복된 카드 조합을 막기 위한 집합 자료형 초기화
5. drawIdx → 뽑은 카드의 인덱스

• 카드를 뽑으면 visited 에 True 표시 후 drawList 에 담기
• 다 뽑으면 다시 visited 에 False 표시하기
• visited 조건문 : 반복문 돌릴 때 나온 값과 drawList 안에 있는 값(= True )의 중복방지를 위함
• "".join(drawList) : return 시 drawList 안의 선택된 K개의 값들을 하나의 정수로 만들기