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

문제

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

접근방법

1. 카드 뽑는 함수인 def pick

result : 카드를 합쳐 만든 문자

n : 뽑은 카드 수

picked : 이미 뽑은 카드의 idx 배열

• n == k  이면 다 뽑은거
  • 중복확인 하기 → 중복되지 않았으면 result에 저장하기
  • 재귀부분
    • if 카드 인덱스가 picked에 없으면 뽑은 카드 인덱스 추가하기

1. 재귀로 푼 나의 코드

import sys

# 카드의 개수를 입력받음
n = int(input())
# 뽑을 카드의 개수를 입력받음
k = int(input())
# 카드 목록을 입력받음
cards = [sys.stdin.readline().strip() for _ in range(n)]

# 중복된 조합을 저장할 리스트
card_list = []

def pick(result, n, picked):
    # 현재 선택한 카드의 개수가 k와 같으면
    if n == k:
        # 결과가 이미 리스트에 없다면 추가
        if result not in card_list:
            card_list.append(result)
        return

    # 모든 카드 인덱스를 순회
    for card_idx in range(len(cards)):
        # 현재 카드 인덱스가 이미 선택되지 않았다면
        if card_idx not in picked:
            # 카드 인덱스를 선택 리스트에 추가
            picked.append(card_idx)
            # 현재 결과에 선택한 카드를 추가
            new_result = result + cards[card_idx]
            # 다음 카드를 선택하기 위해 재귀 호출
            pick(new_result, n + 1, picked)
            # 선택한 카드를 리스트에서 제거 (백트래킹)
            picked.pop()

# 빈 문자열로 시작하여 카드 선택을 시작
pick("", 0, [])
# 중복되지 않은 카드 조합의 개수를 출력
print(len(card_list))

2. itertools 활용한 코드

 itertools.permutations 

: 주어진 리스트 cards에서 k개의 카드의 순서를 고려하여 선택할 수 있는 모든 가능한 순열을 생성한다.

→ 각 순열을 튜플로 반환한다. ex.("A", "B")

 

 " ".join(배열) 

: 배열의 요소를 합쳐 문자열로 만든다.

→ 이 과정에서 모든 순열이 문자열로 결합된다. ex.("A", "B") → "AB"

 

 set() 

: 중복 제거. set이 중복된 항목들을 자동으로 제거하여, 최종적으로 고유한 조합만 남음

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))))

 

itertools를 활용한 코드가 배로 빠르다는 것을 확인 할 수 있었다.

재귀로 푼 코드

itertools를 활용한 코드

 

팀원분이 알려줘서 사용해봤는데 겁나 빠르고 코드도 한줄만에 끝난다는거 보고 감탄의 이마를 탁 쳤다....