[python] 백준 5568 :: 카드 놓기 (재귀 함수 vs itertools 비교)

이주희·2023년 3월 7일

Algorithm

목록 보기

38/79

[카드 놓기]

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

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

재귀함수 vs itertools 속도 비교

1. 백준 제출 기준

위가 itertools, 아래가 재귀함수 사용한 코드이다.
itertools 쓴 게 압도적으로 빠르다..!

2. 재귀함수

소요 시간: 0.0166ms

3. itertools

소요 시간: 0.0003ms
약 55배 빠름 ㅋㅋ

1. 재귀함수 풀이

import sys
n = int(input())
k = int(input())
cards = [sys.stdin.readline().strip() for _ in range(n)]

# 만든 카드를 담을 배열
card_list = []

# result: 카드를 합쳐 만든 문자
# n: 뽑은 카드 수
# picked: 이미 뽑은 카드의 idx 배열
def pick(result, n, picked):
    # n이 k가 되면 카드를 모두 뽑은 것
    if n == k:
        # 이미 뽑은 카드와 겹치는 지 확인하고,
        if result not in card_list:
            # 겹치지 않으면 카드 배열에 추가
            card_list.append(result)
        return

    for card_idx in range(len(cards)):
        # picked에 card_idx가 있으면 이미 뽑은 카드니까 제외
        if card_idx not in picked:
            # 지금 뽑은 카드의 idx를 뽑은 카드의 idx 배열에 추가
            picked.append(card_idx)
            # 지금 뽑은 카드의 값을 기존에 뽑은 값들 뒤에 더해서 새 변수에 할당
            new_result = result + cards[card_idx]
            # 지금 완성된 카드값, 뽑은 카드 수, 사용한 카드의 idx들
            pick(new_result, n+1, picked)
            # 다음 반복에서는 다른 카드를 뽑을 거니까 지금 뽑은 카드의 idx 제거
            picked.pop()


pick("", 0, [])
print(len(card_list))

2. itertools 풀이

import sys
import itertools
n = int(input())
k = int(input())
cards = [sys.stdin.readline().strip() for _ in range(n)]
print(len(set("".join(i) for i in itertools.permutations(cards, k))))