카드 놓기 - 재귀함수 입문을 위한 순차적 디버깅

조해빈·2023년 3월 6일

백준

목록 보기

7/53

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

출력

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

풀이

전체 답안은 아래와 같다.

- 정답 01 재귀함수 사용하여 순열 구현

import sys
input = sys.stdin.readline
N = int(input().strip())
K = int(input().strip())
cards = []
for _ in range(N): 
    cards.append(str(input().strip()))

arr = [0]*N
num = ''
tmp = ''
result = set()

def permu(n): 
    global num 
    if n==K:
        result.add(num) 
        return
    for i in range(N):
        if arr[i]==0:
            arr[i] = 1
            tmp = cards[i]
            num += tmp
            permu(n+1)
            arr[i] = 0
            num = num[:-len(tmp)]

permu(0)
print(len(result))


- 정답 02 순열 라이브러리 사용

import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input().strip())
K = int(input().strip())
cards = []
for _ in range(N): 
    cards.append(str(input().strip()))

numlst = []
for t in permutations(cards, K):
	num = ''.join(t)
	numlst.append(num)
print(len(set(numlst)))

재귀함수에 대해 서술하기 전, 복습하면서 또 깨달은 것은 아직도 인풋 받는 수행에 대해 실수가 많단 거다...
다른 것보다도 카드의 숫자들을 받는 리스트를 입력받는 데에 다음과 같은 실수가 있었다.

# 01
# cards = list(str(input()) for _ in range(N))

# 02
# cards = []
# for _ in range(N): 
#     cards.append(str(input().strip()))

print(cards)

위 두 코드 중 옳은 것은?
이 두 케이스는 최종적으로 다른 결과를 낳는다.

01

cards = list(str(input()) for _ in range(N))

풀이과정 상 숫자와 숫자를 string으로 조합하여 붙이기 때문에 input을 str으로 받는데, 이때 위 코드는 개행문자 \n를 제거하지 않아 이후의 함수 실행에서 의도하지 않은 오류적 결과를 낳는다.

02

cards = []
for _ in range(N): 
     cards.append(str(input().strip()))

for문의 여부를 떠나 이 코드에서는 strip()을 이용했으므로 그러한 상황이 없다.

하....
입력받는 코드가 아직도 어렵다니....

어쨌든
이제부턴 글에선 재귀 함수 이용 건만 다루겠다.
def 내 모든 행에 중단점을 걸어 디버깅하면서 이해했다.

먼저 예제 입력을 실행해보겠다.
4
2
1
2
12
1

풀이할 방식은 이러하다.

주어지는 카드의 개수만큼 빈 칸을 그린다. 내가 그려보겠다. 예제 1 에서 N==4이므로 빈 칸 4개가 필요하다.
ㅁ ㅁ ㅁ ㅁ
우린 주어진 카드 중 K개 만큼을 뽑아 가능한 조합을 모두 만들 예정이다.
예제 1 에서 K==2이다. 고로 순서대로 첫번째 빈 칸에 표시한 뒤 두번째 빈 칸에 표시, 첫+두 조합 기록 -> 두번째 칸에 표시 지우고 세번째 빈 칸에 표시, 첫+세 조합 기록 -> 세번째 칸에 표시 지우고 네번째 빈 칸에 표시, 첫+네 조합 기록 -> 첫번째 칸에 표시 지우고 -> 두번째 빈 칸에 표시 -> 첫번째 빈칸에 표시, 두+첫 조합 기록 -> 첫번째 칸에 표시 지우고 세번째 빈 칸에 표시, 두+세 조합 기록 -> ..... 이런 식으로 모든 조합을 기록할 것이다. (기록되는 내용은 결과적으로는 중복될 수도 있다. 이후 이걸 set()로 중복 제거할 것이다.)

위의 텍스트는 그림으로 설명하면 아래처럼 된다.

v ㅁ ㅁ ㅁ
v v ㅁ ㅁ
v ㅁ v ㅁ
v ㅁ ㅁ v
ㅁ ㅁ ㅁ ㅁ
ㅁ v ㅁ ㅁ
v v ㅁ ㅁ
ㅁ v v ㅁ (여기까지가 텍스트 내용)
ㅁ v ㅁ v
ㅁ ㅁ ㅁ ㅁ
ㅁ ㅁ v ㅁ
v ㅁ v ㅁ
ㅁ v v ㅁ
ㅁ ㅁ v v
ㅁ ㅁ ㅁ ㅁ
ㅁ ㅁ ㅁ v
v ㅁ ㅁ v
ㅁ v ㅁ v
ㅁ ㅁ v v

하... 나 너무 열심히 적는 듯...
어쨌든 위를 토대로 이를 코딩에 적용하면 ㅁㅁㅁㅁ의 역할을 할 보관소는 arr=[]가 되고 arr는 비유하자면 1열짜리 체크표라서 밑으로 내용을 이어 쓰는 게 아니라 계속 그 1열이 갱신되는 거다. 고로 arr의 바뀌는 내용마다를 기록할 보관소는 result며, num='', tmp=''는 메모장 같은 거다.

예제 입력 1

1~2. 함수 permu() 선언, n==0부터 함수가 실행된다.

3. n==0이다. 고로 이 if은 패스한다.
4. for문에 도착했다. 당연하게도 i==0부터 for문 시작.
5. 현재 i==0이므로 if문에 걸린다.
6. if문 내용은 arr[0]의 값을 (현재 0) 1로 재할당하는 일이다.
7. 좌측의 디버거 창에서 arr의 인덱스0째 요소가 1로 바뀐 걸 확인할 수 있다. 다음 수행은 임시 보관함 역할인 스트링형 변수 tmp에 리스트 cards의 i==0번째 요소의 값을 넣는 일.
8. 좌측의 디버거 창에서 tmp에 cards[i(현재i==0)] 의 값 "1"이 넣어졌음을 확인할 수 있다. 다음으로 같은 값을 역시 보관함 역할의 변수 num에 넣으라는 수행을 해야할 차례다.
9. num에 cards[i(현재i==0)] 의 값 == tmp의 값 == "1"이 들어갔다. 다음으로는 permu(1)를 실행할 차례다.
10. permu(1)이 실행됐다. 현재 n==1이므로 해당 if문을 건너뛸 것이다.
11. for문에 도착했다. 당연히 i==0부터 for문 시작.
12. 현재, i==0, n==1임을 좌측 디버거 창에서 확인할 수 있고 이 상태에서 if문에 도달. arr[0]의 값이 0이냔 질문이다. 현재 우리가 가진 arr는 앞서 실행했던 permu(0) 덕분에 arr[0]의 값이 1이다. 고로 이 if을 튕기게 된다.
13. if을 튕겼다. 다시 for문 문턱으로 돌아와 i++ 즉 i==1이 될 차례다.
14. 현재, i==1이다. 다시 arri의 값이 0이냔 if에 도달. 우리가 지금 가진 arr는 arr[1]의 값이 0이다. 고로 이 if에 걸려서 if이 실행된다.
15. 주어진 수행은 arri = 1하는 일이다. 수행할 것이다.
16. 수행했다. arr가 현재 [1, 1, 0, 0]임을 확인할 수 있다. 이제 cardsi의 값(cards[1]==2)을 임시보관용 변수 tmp에 넣을 것이다.
17. tmp에 cardsi의 값(cards[1]==2)이 들어갔다. 현재 tmp가 2임을 확인할 수 있다. 이제 스트링 변수인 num의 끝에 현재의 tmp를 갖다 붙일 것이다. 이때, global 변수인 num은 아까 우리가 실행한 permu(0) 덕에, 현재 num은 '1'인 상태다. 여기에 현재 tmp인 '2'가 갖다 붙여지는 수행을 이제 하는 것이다.
18. 수행됐다. 스트링 변수 num은 이제 '12'임을 확인할 수 있다. 다음으로 할 일은 permu(2)이다.
19. permu(2)가 실행되기 시작했다. 말인즉 현재 n==2이고, 이는 좌측의 디버거 창에서 확인할 수 있다. 현재 n이 K냐는 if문의 초입에 도달했다. 알다시피 우리가 입력 받았던 인풋값 K==2이므로, if문 안으로 들어가게 될 것이다.
20. set 변수 result에 현재 스트링 변수 num의 값을 add하라는 수행이 주어졌다. 수행할 것이다.
21. 수행했다. 비어 있던 set 변수 result에 이제 첫 요소로 '12'라는 값이 할당되었음을 좌측의 디버거 창에서 확인할 수 있다. 이제 return 하라는 수행이 주어졌다. return이란 함수의 종료를 뜻하고, 재귀 함수 안에서의 return이란 즉 현재 실행되고 있는 함수가 실행되었던 지점으로의 복귀를 뜻한다. 말인즉 지금 우리는 permu(2)를 수행하고 있었고(좌측의 디버거 창에서 n 값 확인 가능), permu(2)는 여기서 종료되며 이제 아까 수행하던 permu(1)을 계속 이어서 수행할 것이다. 어디서부터? permu(2)가 실행됐던 그 지점에서부터.
22. 자, 이제 아까 수행하던 permu(1)의 아까 그 부분 그 지점으로 왔다. 현재 n==1, i==0, tmp=='2'임을 좌측의 디버거 창에서 확인할 수 있다. 이어지는 수행 내용은 arr[i](현재i==0)의 값을 다시 0으로 재할당하라는 내용이다. 이는 위에서 내가 열심히 그림으로 설명한 부분 중 v 표시를 지워 해당 체크칸을 ㅁ로 다시 원복시키는 수행 중 하나다.
다시 말하면 현재 우리는 cards의 인덱스0째 요소로 cards의 다른 요소들을 조합하고 있다. 우린 그에 대한 첫번째 실행인 v v ㅁ ㅁ을 방금 완수한 것이다. 이 다음 우린 [1, 1, 0, 0] 즉 v v ㅁ ㅁ에서 v ㅁ v ㅁ, v ㅁ ㅁ v도 조합하여 이 내용들도 다 result에 넣을 계획이다.
지금 가장 먼저 해야할 일은 v v ㅁ ㅁ을 v ㅁ ㅁ ㅁ로 한 차례 원복시키는 일이다. 이제 이걸 수행할 것이다.
23. 수행했다. [1, 1, 0, 0]이었던 arr가 현재 [1, 0, 0, 0]이다. 현재 num은 '12'이다. 우린 arr의 인덱스0째 요소에 대한 조합을 더 찾아야 하므로, num에서부터 arr의 인덱스0째 요소의 내용은 유지한 채 arr의 인덱스1째 요소의 내용만 지우는 수행을 해야하는 것이다.
24. 수행했다. 현재, num은 '1'이다. 현재 i==1인데, 이제 permu(1)내의 반복문 i==1번째를 다 돈 것이다. 이제는 i==2번째 반복문을 돌 차례이다.
25. 현재, i==2이다. 반복문 내용이 다시 첨부터 시작됐다. arri냐는 if문에 걸리게 된다. 이제 if문 안으로 들어가게 될 것이다.
26. arri의 값을 1로. v ㅁ v ㅁ.
27. 이제 arr==[1, 0, 1, 0]이다. tmp에 cards[2](현재i==2)=='12' 할당하는 수행에 도달했다. 수행하면 tmp=='12'.
28. 방금처럼 스트링 변수 num의 끝에 tmp=='12'를 갖다 붙인다. 아까 num=='1'이었고 이제 '112'.
29. 지금 우리는 permu(1)의 i==2번째 반복문 수행 중에 있다. 이제 다음으로 할 일은 다시금 permu(2)이다.
30. permu(2) 즉 n==2라서 맨 위인 탈출 if문에 걸린다. if문 안으로 들어가게 될 것이다.
31~32. 현재 num은 곧 현재 arr==[1, 0, 1, 0] == v ㅁ v ㅁ == 'permu(1)의 i==2째 반복문의 결과물', "112"인 상태다. result()에 add하면 오름차순으로 요소가 추가되어 return 시 이제 result=={'112', '12'}가 되었다. 다음으론 permu(1)의 i==2째 반복문을 이어서 수행할 것이다. 어디서부터? permu(2)가 실행됐던 그 지점에서부터.
33~34. 아까와 같이 arr와 num의 한 단계 원복에 대한 수행이다. 아래 두 수행을 수행하면 이제 permu(n==1)의 i==3째 반복문이다.
35~사십일번인가이번인가하여간몇번. 4번째 카드와 1번째 카드의 조합을 result에 이제 permu(2)의 마지막 i==3번째 반복문도 마쳤고(N==4, ==range(0, 4), i는 0~3) return하면 말인즉 아까 permu(1)의 수행 중 아까 permu(2)가 불러와진 시점으로 돌아온다.
4?. permu(1)의 i==3째 반복문 안이다. 이제 v ㅁ ㅁ v 의 네번째 v를 지우는 수행이 목전에 있다.
4??. 수행했고, 이제 v ㅁ ㅁ ㅁ 의 첫번째 v를 지우는 수행이 목전에 있다. 이것이 permu(0)의 i==0째 반복문 안의 permu(1)의 i==3째 반복문의 끝, 즉 permu(0)의 i==0 반복문의 끝이다.
4?. 이런 식으로 하나의 permu 인스턴스가 종료된다. 아래의 수기 도표가 전체 이 풀이의 플로우다.