[백준] 5568번: 카드 놓기

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

initial

Typical backtracking question BUT we are not gonna pass index+1 as parameter to our dfs because if we are at index=2, we don't want to skip traversals for index=0 and index=1, as mentioned in the question.

solution

my solution using visited list

n= int(input())
k = int(input())
lst = []
for  _ in range(n):
    lst.append(int(input()))

ans = set()
visited= [False for _ in range(n)]

def dfs(tmp):
    if len(tmp)==k:
        ans.add(int(''.join(map(str,tmp))))
        return

    for i in range(n):
        if not visited[i]:
            tmp.append(lst[i])
            visited[i]=True
            dfs(tmp)
            tmp.pop()
            visited[i]=False
dfs([])
print(len(ans))

using permutations

since order matters for this q, u can use permutations

from itertools import permutations

n = int(input())
k = int(input())
cards = []

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

result = set()

for i in permutations(cards, k):
    result.add(''.join(i))

print(len(result))

complexity

2^n time and n space?

nope

In your code, you're generating all permutations of k cards from a total of n cards and then storing them in a set to eliminate duplicates. The time complexity of generating permutations is determined by the number of permutations, and it's O(n! / (n-k)!). The space complexity depends on how many unique permutations are generated and stored in the result set.

Let's analyze the time and space complexity of your code:

Time Complexity:
1. Creating a list of cards: This is O(n) as it involves iterating through the n cards.
2. Generating permutations: This part has a time complexity of O(n! / (n-k)!) because you're generating all possible permutations of k cards from n cards.
3. Storing permutations in a set: The add operation in a set is generally close to O(1), and you do this for each permutation. The number of unique permutations generated is also O(n! / (n-k)!).

So, the overall time complexity of your code is dominated by the permutation generation, which is O(n! / (n-k)!).

Space Complexity:
1. List to store cards: O(n) space is used for storing the list of cards.
2. The result set: The space required for the result set depends on how many unique permutations are generated. In the worst case, if all permutations are unique, it could be O(n! / (n-k)!).

Therefore, the space complexity is O(n) + O(n! / (n-k)!).

Keep in mind that for large values of n and k, the time and space complexity of generating permutations can be quite high.