[BOJ] 5568. 카드 놓기

Python3

문제

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

키워드

• 자료 구조
• 브루트포스 알고리즘
• 해시를 사용한 집합과 맵
• 백트래킹

문제 풀이

문제 요구사항

카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다.
이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다.
만들 수 있는 정수는 모두 몇 가지일까?

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램

변수 및 함수 설명

• n: 카드 장수
• k: 뽑을 카드 개수
• card: 카드 리스트
• st: k개를 선택해서 만들 수 있는 정수 리스트

풀이

(입력 및 선언)

• 카드 장수와 뽑을 카드 개수를 차례로 입력받는다.
• 카드 리스트에 입력받은 카드들을 저장한다.

(경우의 수 계산)

• 순열 함수를 사용해 경우의 수를 계산한다.
• 모든 경우의 수를 돌면서 st 리스트에 나란히 붙인 정수를 저장한다.

(최종 출력)

• 중복을 없앤 st 리스트 개수를 출력한다.

최종 코드

from itertools import permutations

card = []
st = []

n = int(input())
k = int(input())

for _ in range(n):
    card.append(input())

for i in permutations(card, k):
    st.append(''.join(i))

print(len(set(st)))

피드백

join 함수가 생각이 안 나서 나란히 붙이는 부분에 애를 먹었다.
처음엔 리스트에 해당 정수가 있는지 매번 확인하도록 코드를 짰으나, 모든 정수를 다 나열한 후 한 번에 중복을 제거하는 것이 더 효율적이라 코드를 수정했다.