[백준][5568] 카드 놓기

1. 문제

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

 

 

2. 풀이

 

일단, 조합을 사용해서 모든 수에 대한 값을 리스트에 넣은 후 set을 통해 중복값을 제거한 후 남은 것의 개수를 반환하면 될 것 같다. 

 

• 정수 n 입력
• 정수 k 입력
• for문 (n번 반복) : 카드 숫자 입력(문자열로 입력 받음)
  • 카드 k개 조합

근데 여기서.. 2중 for문으로 조합을 하려고 했는데 2중 for문은 k가 2인 경우에만 해당이 된다.. 그러면 만약 k가 4이면? 4중 for문???? 이러면 시간 복잡도에 문제가 생길 것이다. 흠.... 어떻게 해야 할까?

 

순열 또는 조합을 사용하면 될 것이라고 생각을 했다.

그러면, 카드를 무작위로 조합해야 할까? 아니면, 순서까지 따져서 조합해야 할까? 예제1로 시뮬레이션을 해보았다.

 

1  2   12  1 중에 2개를 뽑아서 만들 수 있는 정수 
- 1/2 = 12
- 1/12 = 112
- 1/1 = 11
- 2/1 = 21
- 2/12 = 212
- 2/1 = 21
-12/1 = 121
- 12/2 = 122
- 12/1 = 121
- 1/1 = 11
- 1/2  = 12
- 1/12 = 112

12,112,11,21,212,21,121,122,121,11,12,112
=> 12, 112, 11, 21, 212, 121, 122 => 7개

1  2   12  1 

만약에 3개를 뽑아야 한다면?

- 1/2/12 = 1212

- 1/2/1 = 121

- 1/12/2 = 1122

- 1/12/1 = 1121

- 1/1/2 = 112

- 1/1/12 = 1112

- 2/1/12 = 2112

- 2/1/1 = 211

- 2/12/1 = 2121

- 2/12/1 = 2121

- 2/1/1 = 211

- 2/1/12 = 2112

...

 

이렇게 보니까 고유의 순서가 있다고 가정하고 조합을 한 후에 set 함수에 넣어서 중복을 제거하면 될 것 같다. 

 

 

3. 내가 짠 코드

• permutarion 후 중복 제거 ( itertools라이브러리 사용)

 

import itertools

n = int(input())    # 총 카드의 수

k = int(input())    # 선택할 카드의 수

cards=[]            # 카드 번호 저장할 리스트

result = []         # 조합을 저장할 리스트

for i in range(n):  # 카드 번호 입력받기

    cards.append(input())

for permutated in itertools.permutations(cards,k):

    val = ""

    for p in permutated:

        val+=p

    result.append(val)

print(len(set(result)))

 

 

 

4. 다른 사람이 짠 코드

 

다른 사람들이 짠 코드를 보니까 내가 생각했던 1) permutation후 중복을 제거하는 방식 또는 2) 재귀방식을 사용한 것 같다. 

 

https://jjineu.tistory.com/23

[백준/python] 5568_카드놓기

 

근데 이 코드를 보고 내 코드를 살짝 고쳐봤다 ㅎㅎ permutation후 문자열을 합칠 때 join 함수가 있다는 것을 잊고 +=으로 했는데 join으로 바꿔서 다시 제출해봤다.

 

시간이 조금 줄었다 !!

 

그리고 위 게시글에서 다른 방법으로 사용한 백트래킹에 대해 공부해보았다!

https://yeonnnnny.tistory.com/132

[알고리즘] 백트래킹(BackTracking)

 

백트래킹으로 구현한 코드

 

n = int(input())    # 총 카드의 수

k = int(input())    # 선택할 카드의 수

cards=[]            # 카드 번호 저장할 리스트

for i in range(n):  # 카드 번호 입력받기

    cards.append(input())

 

# 백트래킹

check = [0]*n

temp = []

result = set()

def card(N):

    if N==k:

        result.add(''.join(temp))

        return

    for i in range(n):

        if check[i]:

            continue

        check[i] =1

        temp.append(cards[i])

        card(N+1)

        check[i] = 0

        temp.pop()

card(0)

print(len(result))