[COS PRO 1급 #4-8] n번째로 작은 수 구하기

문제설명

1 이상 9 이하 숫자가 적힌 카드를 이어 붙여 숫자를 만들었습니다. 이때, 숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 구하려 합니다.

예를 들어, 숫자 카드 1, 2, 1, 3로 만들 수 있는 수를 작은 순으로 나열하면 [1123, 1132, 1213, 1231, 1312, ... , 3121, 3211]입니다. n이 1312라면, 숫자 카드를 조합해 만든 수 중 n은 n은 5번째로 작은 수입니다.

숫자 카드를 담은 리스트 card, 수 n이 매개변수로 주어질 때 숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 return 하도록 solution 함수를 완성해주세요.

매개변수 설명

카드에 적힌 숫자를 담은 리스트 card, 수 n이 solution 함수의 매개변수로 주어집니다.

* card는 길이가 9 이하인 리스트입니다.
* card의 원소는 1 이상 9 이하인 자연수입니다.
* n은 999,999,999 이하인 자연수입니다.
* n의 자릿수는 리스트 card의 길이와 같습니다.
* n의 각 자리의 숫자는 1 이상 9 이하입니다.

return 값 설명

숫자 카드를 조합해 만든 수 중에서 n이 몇 번째로 작은 수인지 return 해주세요.

* 만약, n을 만들 수 없다면 -1을 return 해주세요.

예시

| card | n | return |
|----|----|----|
| [1, 2, 1, 3] | 1312 | 5 |
| [1, 1, 1, 2] | 1122 | -1 |

예시 설명

예시 #1
앞서 설명한 예와 같습니다.

예시 #2
숫자 카드를 조합하면 [1112, 1121, 1211, 2111]를 만들 수 있습니다. 따라서 1122는 만들 수 없습니다.

문제 코드

def solution(card, n):
    # 여기에 코드를 작성해주세요.
    answer = 0
    return answer

풀이

nums = []

# card로 만들 수 있는 숫자 조합 리스트 nums 구하기
# card_cnt: 주어진 card의 숫자별 개수 리스트
# used_cnt: 숫자 조합을 만들기 위해 사용한 숫자별 개수 리스트
def num_list(card_cnt, used_cnt, num):
	for i in range(1, 10):
		if used_cnt[i] < card_cnt[i]:
			used_cnt[i] += 1
			num_list(card_cnt, used_cnt, num*10+i)
			used_cnt[i] -= 1
	if sum(used_cnt) == sum(card_cnt):
		nums.append(num)

def solution(card, n):

	# 주어진 card의 숫자별 개수 리스트 구하기
	card_cnt = [0]*10
	for i in card:
		card_cnt[i] += 1
	
	num_list(card_cnt, [0]*10, 0)
    
    # 숫자 조합 리스트에서 n의 순서 구하기
	for idx, num in enumerate(nums):
		if num == n:
			return idx+1
	return -1