5568 카드놓기

 

https://www.acmicpc.net/problem/5568

5568번: 카드 놓기

 

N장을 선택해서 조합을 만드는 경우라서 재귀라고 생각을 했다.. 사실 문제 분류가 재귀이기도하지만..

한장을 선택할때마다 카드를선택하고 다시 카드선택을 호출해서 조합을 만들어야하니까 ~ 

이런 느낌으로다 ...!

 

접근은 for문으로 순회하면서 재귀를 이용해 탐색한다는것..

따라서 3가지가 필요했다

1.  원본카드 리스트

2. 선택한카드의 인덱스를담는 스택.

3. 정답배열을 답는 리스트

 

2,3번의 리스트는 조회할때마다 not in을 통해 중복여부를 체크해주고

 

재귀 호출이 종료되면 depth를 복구시켜주고, 선택한카드의 인덱스를 pop해서 다음 카드 조합을 만들수있게해주었다.

 

생각 보다 고생한건 아직 파이썬에 익숙하지가 않아서... 

depth 2에서 만든 변수를 

depth 1에서 동일한 변수명으로 인식되면 영향이 미친다는것이다..파이썬의 클로져라는 것이있는데

파이썬 closure
 => 함수가 다른 함수 내에 중첩될때, 내부 함수가 외부함수의 범위에 접근할 수 있는 것을 의미한다.  
 => 아 재귀에서 값을 이전 단계에서 값을 가지고 있다는 느낌이 안들고 계속 값이 유지된다

 

그래서 변수명을 구분지어서 만들어 줘야한다..

def combin_card(combine_num:str,depth:int,card_list:list,answer_list:list,used_card:list):
    if depth == 0:
        if combine_num not in answer_list:
            answer_list.append(combine_num)
        return
    ## 인덱스를 사용해야하는 이유는 .. 동일 숫자카드에 대해서 depth분기가 2개면 괜찮은데 3개이상하면 다른 경우도 생기기 때문?
    for card_index in range(len(card_list)):
      if card_index not in used_card:
        # 파이썬은 스택이 없지만 list 로 스택 흉내를 낼수있다 push는 append pop은 pop
        used_card.append(card_index)
        # 글자 합치기
        new_combine_num=combine_num+card_list[card_index]
        depth-=1
        combin_card(new_combine_num,depth,card_list,answer_list,used_card)
        # return을 받고 다시 윗단계로 복구시켜줌.
        depth += 1
        used_card.pop()


card = int(input())
card_list=[""]*card
depth = int(input())

for i in range(card):
    card_list[i] = str(input());

combin_card("",depth,card_list,answer_list,used_card)

print(answer_list)
print(len(answer_list))

 

함수에 파라미터가 쓸데없이 들어간 느낌이긴한데.. 뭔가 넣어줘야할것같았다... 하지만 이것도 클러저때문에 상관없는듯하다

아래와 같이 함수 위에만 잘 선언해주면 알아서 접근한다..

answer_list=[]
used_card=[]
def combin_card(combine_num:str,depth:int):
    if depth == 0:
        if combine_num not in answer_list:
            answer_list.append(combine_num)
        return
    ## 인덱스를 사용해야하는 이유는 .. 동일 숫자카드에 대해서 depth분기가 2개면 괜찮은데 3개이상하면 다른 경우도 생기기 때문?
    for card_index in range(len(card_list)):
      if card_index not in used_card:
        # 파이썬은 스택이 없지만 list 로 스택 흉내를 낼수있다 push는 append pop은 pop
        used_card.append(card_index)
        # 글자 합치기
        # 아 클로져때문에 변수명을 구분
        new_combine_num=combine_num+card_list[card_index]
        depth-=1
        combin_card(new_combine_num,depth)
        # return을 받고 다시 윗단계로 복구시켜줌.
        depth += 1
        used_card.pop()


card = int(input())
card_list=[""]*card
depth = int(input())

for i in range(card):
    card_list[i] = str(input());

combin_card("",depth)

print(answer_list)
print(len(answer_list))