[백준] 1759번: 암호 만들기

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

initial

so another backtracking question that is a bit harder tha n+m (1) question.

My initial attempt printed out a lot of wrong additional test cases so I went back to what backtracking means.

Backtracking is after you reached your recursion-break-out logic, you backtrack your path and everything back to your previous state. So if you have added vowel and consonant counts for your dfs search, then after you break out of your recurison, you have to minus them back to reach the previous state.

my initial wrong code (see below for correct code)

        if not visited[i] and (not tmp or lst[i]>tmp[-1]):
            if lst[i] in vowels:
                vowel_cnt+=1
            else:
                other_cnt+=1
            visited[i]=True
            tmp+= lst[i]
            dfs(i+1, vowel_cnt, other_cnt,tmp)

            tmp=tmp[:-1]
            visited[i]=False

Another imporant thing is that the paths have to be strictly increasing, so you need to check it via

(not tmp or lst[i]>tmp[-1])

So if tmp is empty you just add lst[i] (to prevent list index out of range error) and if it is not empty, we check the last element of our tmp string and see if the incoming value is bigger than our last element in the tmp string.

so my corrected solution:

n,m = map(int,input().split())
lst = list(map(str,input().split()))
lst.sort()
visited=[False for _ in range(m)]
tmp=''
vowels= ['a','e','i','o','u']

def dfs( vowel_cnt, other_cnt,tmp):
    count =0
    for i in range(len(lst)):
        if len(tmp)==n:
            if vowel_cnt>=1 and other_cnt>=2:
                count+=1
                print(tmp)
                return
        if not visited[i] and (not tmp or lst[i]>tmp[-1]):
            visited[i]=True
            tmp+= lst[i]
            if lst[i] in vowels:
                vowel_cnt+=1
                dfs(vowel_cnt, other_cnt,tmp)
                tmp=tmp[:-1]
                visited[i]=False
                vowel_cnt-=1
            else:
                other_cnt+=1
                dfs( vowel_cnt, other_cnt,tmp)
                tmp=tmp[:-1]
                visited[i]=False
                other_cnt-=1

dfs( 0,0,tmp)

btw you don't have to pass index+1 as parameter to your dfs search because https://brian6484.github.io/data%20structure%20&%20algorithms/2022/12/08/DFS.html#h-basic-dfs-with-backtracking

my solution is pretty lengthy so let's try to make it more concise by reducing the duplicate code

model solution

This model ans is half the time runtime so it is 2x more time efficient.

When count==l, which is the length of the combination of tmp string, then we count the vowels and consonants. If it is correct, we print and return. For backtracking, we pop the last element and check for other value in our words list via iterating through the next index (i+1).

import sys

l, c = map(int, sys.stdin.readline().split())
words = sorted(list(map(str, sys.stdin.readline().split())))
answer = []

def back_tracking(cnt, idx):
    if cnt == l:
        vo, co = 0, 0

        for i in range(l):
            if answer[i] in ['a', 'e', 'i', 'o', 'u']:
                vo += 1
            else:
                co += 1

        if vo >= 1 and co >= 2:
            print("".join(answer))

        return

    for i in range(idx, c):
        answer.append(words[i])
        back_tracking(cnt + 1, i + 1)
        answer.pop()

back_tracking(0, 0)

complexity

Time Complexity:

• In the dfs function, you are iterating over the lst list using a loop.
• In each iteration, you are checking conditions and making recursive calls.
• In the worst case, the code explores all possible combinations.
• The time complexity is exponential, specifically O(2^n), where n is the length of the lst list.

Space Complexity:

• The primary contributors to space complexity are the recursive call stack and the tmp string.
• The recursive call stack depth can go up to n in the worst case, corresponding to the length of the combination.
• The tmp string stores the current combination, which can have a maximum length of n.
• The visited list and vowel_cnt and other_cnt variables occupy a constant amount of space relative to the input size.
• Therefore, the space complexity is O(n) in most practical cases.

In summary, the time complexity of the code is exponential (O(2^n)), while the space complexity is linear (O(n)) in most cases. This means that the code may become slow for large values of n due to the exponential time complexity. You can optimize this code further, but generating all combinations with these constraints inherently has exponential complexity.