[Python/Baekjoon] B1759. 암호 만들기

💬 문제

문제 난이도: 골드 5

문제 링크: https://www.acmicpc.net/problem/1759

문제 설명

암호는 최소 1개의 모음과 2개의 자음으로 이루어져 있다.
암호의 길이는 L일 때, 주어진 배열에 담긴 알파벳으로 만들 수 있는 경우의 수를 모두 반환하라.
암호를 구성하는 알파벳은 오름차순 정렬되어 있다. 'abc' 가능하지만 'bca'는 불가능하다.

❗️접근 방법

DFS, 백트래킹

시간초과 해결 방법

1. ❌ 시간초과 코드
   1) arr로 만들 수 있는 모든 경우의 수를 다 구한다.
   2) 만들어진 결과물로 모음이 1개 이상, 자음이 2개 이상인 경우를 체크(checkValidation 사용)
2. ✅ 통과 코드
   1) arr를 정렬하고, 모음 배열(arr1), 자음 배열(arr2)로 나눔.
   2) 모음 배열에서 v개(v>=1) 사용해서 만들 수 있는 경우의 수 구함.이때 (L-v>=2 이어야 함)
   3) 자음 배열에서 c개(c>=2) 사용해서 만들수 있는 경우의 수 구함. 이때 (L-c>=1이어야 함)
   4) 만들어진 경우의 수를 연결(elem1+elem2)하고 각각의 경우를 정렬해서 결과배열(result)에 추가

코드(❌시간초과)

import sys
input = sys.stdin.readline

L, C = map(int, input().split(' '))
arr = list(input().rstrip().split(' '))
arr.sort()

s = set(['a', 'e', 'i', 'o', 'u'])
        
def checkValidation(word):
    v = 0
    c = 0
    for char in word:
        if char in s:
            v += 1
        else:
            c += 1
    if v>= 1 and c>=2:
        return True
    return False

result = set()
def dfs(curStep, temp,  visited, start):
    if curStep == L:
        if checkValidation(temp):
            w = ''.join(sorted(list(temp)))
            result.add(w)
        return
        
    for i in range(start, C):
        if not visited[i]:
            visited[i] = 1
            dfs(curStep+1, temp+arr[i], visited, start+1)
            visited[i] = 0

def solution():
    global result
    for i in range(C):
        visited = [0] * C
        visited[i] = 1
        dfs(1, arr[i], visited, i)
    result = list(result)
    result.sort()
    for elem in result:
        print(elem)

solution()

코드(✅ 통과)

import sys
input = sys.stdin.readline

L, C = map(int, input().split(' '))
arr = list(input().rstrip().split(' '))
vowels = set(['a', 'e', 'i', 'o', 'u'])
arr1 = []
arr2 = []
for char in arr:
    if char in vowels:
        arr1.append(char)
    else:
        arr2.append(char)

s1 = []
s2 =[]
def dfs(arr, visit, curStep, limit, temp, start, flag):
    if curStep == limit:
        if flag == 1:
            s1.append(temp)
        else:
            s2.append(temp)
        return
    for i in range(start, len(visit)):
        if not visit[i]:
            visit[i] = 1
            dfs(arr, visit, curStep+1, limit, temp+arr[i], i+1, flag)
            visit[i] = 0

def solution():
    global s1, s2
    result = set()
    for i in range(1, L+1):
        v = i
        c = L-v
        if v >= 1 and c >= 2 and len(arr1)>=v and len(arr2) >=c:
            visited2 = [0] * len(arr2)
            for i in range(len(arr1)):
                visited1 = [0] * len(arr1)
                visited1[i] = 1
                dfs(arr1, visited1, 1, v, arr1[i], i, 1)
            for i in range(len(arr2)):
                visited2 = [0] * len(arr2)
                visited2[i] = 1
                dfs(arr2, visited2, 1, c, arr2[i], i, 2)
        
        for elem1 in s1:
            for elem2 in s2:
                result.add(''.join(sorted(elem1+elem2)))
        s1 = []
        s2 = []
    result = list(result)
    result.sort()
    for elem in result:
        print(elem)


solution()