[백준] 카드 놓기(5568) - python

✏️ 문제

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

🎈 출력

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

🎈 입출력 예

<입력>
4
2
1
2
12
1
<출력>
7

<입력>
6
3
72
2
12
7
2
1
<출력>
68

👩‍💻 내 코드

나는 조합 문제이기 때문에 DFS로 풀었는데 다른 사람들의 코드를 보고 permutations를 사용하는 방법도 있다는 것을 알게 되었다. 두 가지 방법으로 전부 풀어보았다.

• DFS

import sys
sys.setrecursionlimit(10**6)

def dfs(level):
    if level == k:
        num = "".join(num_list)
        if num not in result:
            result.append(num)
        return

    for card in cards:
        if used[card] == cards.count(card):
            continue

        used[card] += 1
        num_list.append(str(card))
        dfs(level+1)
        used[card] -= 1
        num_list.pop()


if __name__ == "__main__":

    n = int(input())
    k = int(input())
    used = [0] * 100
    result = []
    num_list = []

    cards = [int(input()) for _ in range(n)]

    dfs(0)

    print(len(result))

• permutations 이용

import sys
from itertools import permutations

if __name__ == "__main__":

    n, k = int(sys.stdin.readline()), int(sys.stdin.readline())

    cards = [int(input()) for _ in range(n)]
    result = set()
    for i in list(permutations(cards, k)):
        result.add("".join(list(map(str, i))))

    print(len(result))

확실히 라이브러리를 사용하는게 속도는 느리지만 코드가 훨씬 간결해져서 깔끔하고 가독성이 좋은 것 같다. 시간초과만 안나면 라이브러리 사용하는게 좋을듯 하다.

💡 새롭게 배운 것

• itertools 라이브러리의 permutations : 리스트의 모든 순열을 반환한다.
• set()
  • 중복 불가
  • 순서 없음
  • 원소 추가할 때 append가 아닌 add