[파이썬 코딩] Cos Pro 1급 4차 문제8 - n번째로 작은 수 구하기

1 ] 문제

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 해주세요.

---

 

2 ] 해답 

def func_a(card):
  card_count = [0] * 10
  for card_i in card:
    card_count[card_i] += 1
  return card_count

num_list = []
def func_b(level, max_level, num, current_count, max_count):
  if level == max_level:
    num_list.append(num)
  return

  for i in range(1, 10):
    if current_count[i] < max_count[i]:
       current_count[i] += 1
       func_b(level + 1, max_level, num * 10 + i, current_count, max_count)
       current_count[i] -= 1

def func_c(list, n):
  if n in list:
     return list.index(n) + 1
  return -1

def solution(card, n):
  card_count = func_a(card)
  func_b(0, len(card), 0, [0] * 10, card_count)
  answer = func_c(num_list, n)
  return answer

 

 

 

- 헷갈렸던 부분 순차해석

1) func_a 함수 

card = [1, 2, 1, 3]

card_count = [0] * 10
for i in card:
  card_count[i] += 1
print(card_count)

-- 결과값 (card_count)

[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]

 

2) func_b 함수 

card = [1, 2, 1, 3]

num_list=[]
def func_b(level,max_level,num,current_count,max_count):
   if level == max_level:
      num_list.append(num)
      print(num_list)
   return

-- num_list 전체값 출력

[1123]
[1123, 1132]
[1123, 1132, 1213]
[1123, 1132, 1213, 1231]
[1123, 1132, 1213, 1231, 1312]
[1123, 1132, 1213, 1231, 1312, 1321]
[1123, 1132, 1213, 1231, 1312, 1321, 2113]
[1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131]
[1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311]
[1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112]
[1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121]
[1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211]

 

for i in range(1,10):
  if current_count[i]<card_count[i]:
    current_count[i]+=1
    print(current_count)

-- current_count 출력값

[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 1, 0, 0, 0, 0, 0, 0]

 

func_b(level+1,max_level,num*10+i,current_count,max_count)
current_count[i]-=1
print(current_count)

-- current_count[i]-=1 한 current_count 결과값

[0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 2, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 1, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

3) solution 함수

def solution(card,n):
card_count = func_a(card)
func_b(0,len(card),0,[0]*10,card_count)
answer = func_c(num_list,n)
return answer

card1 = [1, 2, 1, 3]
n1 = 1312
ret1 = solution(card1, n1)

- card_count : [0, 2, 1, 1, 0, 0, 0, 0, 0, 0]

- num_list : [1123, 1132, 1213, 1231, 1312, 1321, 2113, 2131, 2311, 3112, 3121, 3211, 1112, 1121, 1211, 2111]

- n = 1312 대입

- 5번째 위치

def func_c(list,n):
  if n in list:
    return list.index(n)+1
  return -1

list.index(n) +1 값 = 4번째 인덱스 +1 = 5

 

결과값 5 출력