[백준] 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