[백준] 5568 : 카드 놓기
문제
순열, 조합
from itertools import permutations, combinations
순열
itertools.permutations(list,n)
순서를 생각해서 나열하는 것
from itertools import permutations
sets = [1,2,3]
data = permutations(sets, 2)
for i in data:
print(i)
#print
(1, 2)
(1, 3)
(2, 1)
(2, 3)
(3, 1)
(3, 2)
조합
itertools.combinations(list,n)
순서를 생각하지 않고 나열하는 것
from itertools import combinations
sets = ['A', 'B', 'C']
data = combinations(sets, 2)
for i in data:
print(i)
#print
(A, B)
(A, C)
(B, C)
join 함수
파이썬에서 리스트를 문자열로 일정하게 합쳐주는 함수
-
''.join(리스트)
''.join(리스트)
를 이용하면 매개변수로 들어온 ['a', 'b', 'c'] 이런 식의 리스트를 'abc'의 문자열로 합쳐서 반환해주는 함수 -
'구분자'.join(리스트)
'구분자'.join(리스트)
를 이용하면 값과 값 사이에 구분자를 넣어서 하나의 문자열로 만들어줌
예제
a = ['a', 'b', 'c', 'd', '1', '2', '3']
result1 = "".join(a)
print(result1) # abcd123
'_'.join(['a', 'b', 'c'])
# "a_b_c"
풀이
import sys
from itertools import permutations
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
nlist = []
for i in range(n):
a = sys.stdin.readline().strip()
nlist.append(a)
data = list(permutations(nlist, k)) # 순열 (순서 생각)
dict = {}
for i in range(len(data)):
add = ''
for j in range(k):
add = add + data[i][j]
if add not in dict.keys():
dict[add] = 1
print(len(dict))
재귀 이용한 풀이
import sys
nn = int(sys.stdin.readline())
kk = int(sys.stdin.readline())
arr = []
for i in range(nn):
arr.append(sys.stdin.readline().strip())
string = []
result = set()
def splice(arr, n): # 본인은 제외한 것을 리턴해주는 함수
return arr[0:n] + arr[n+1:len(arr)] # arr은 안 건드리고 본인은 제외한 리스트를 새로 만들어서 리턴해주는 것
def setCards(arr, k):
global string
n = len(arr)
if k <= 0 :
result.add(''.join(string))
return
for i in range(n):
string.append(arr[i])
setCards(splice(arr,i), k-1) # 방금 전에 뽑은 것을 리스트에서 제외하고 그 중에서 k-1개 뽑아줘야 함
string.pop() # string을 pop해줘야 복구가 됨
setCards(arr, kk)
print(len(result))
재귀로 혼자 푼 풀이
import sys
n = int(sys.stdin.readline())
k = int(sys.stdin.readline())
card = []
result = []
cur = [] # 현재 뽑은 카드
for i in range(n):
card.append(sys.stdin.readline().strip())
def splice(card, n):
return card[0:n] + card[n+1:len(card)]
def setCards(card, k):
global cur
curlen = len(card) # 뽑힌 것들 제외한 리스트의 길이
if k <= 0: # 카드 다 뽑았을 때
result.append(''.join(cur)) # cur[0]만 하면 처음으로 뽑은 카드만 넣어주게 되므로 안 됨
return # cur 리스트에 있는 모든 원소들을 하나로 이어서 문자열로 만들어야
for i in range(curlen):
cur.append(card[i]) # 뽑은 카드를 cur 리스트에 넣어줌 ['1', '12']
setCards(splice(card,i), k-1)
cur.pop()
setCards(card, k)
print(len(set(result)))
# print(set(result))
Sources
https://blockdmask.tistory.com/468
Author And Source
이 문제에 관하여([백준] 5568 : 카드 놓기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@letsbebrave/백준-5568-카드-놓기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)