240407 [BOJ/백준] 1759. 암호 만들기

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

1759번: 암호 만들기

---

나의 코드

1. 자음, 모음의 갯수를 확인하는 함수와 정렬된 리스트를 만드는 함수를 따로 만든 코드

l, c = map(int, input().split())
alphabet = input().split()
alphabet.sort()


def check(arr):
    c_count = 0  # 자음 갯수
    v_count = 0  # 모음 갯수
    for i in arr:
        if i in 'aeiou':
            v_count += 1
        else:
            c_count += 1

    if c_count >= 2 and v_count >= 1:
        return True
    else:
        return False


def backtracking(arr):
    if len(arr) == l:
        if check(arr):
            print(''.join(arr))

    else:
        for j in range(len(arr), c):
            if arr[-1] < alphabet[j]:
                arr.append(alphabet[j])
                backtracking(arr)
                arr.pop()

for k in range(c-l+1):
    ans = [alphabet[k]]
    backtracking(ans)

 

 

2. 정렬된 리스트를 만들고 자음, 모음의 갯수가 맞는 것만 출력하는 함수

l, c = map(int, input().split())
alphabet = input().split()
alphabet.sort()

def backtacking(length, ans):
    if length == l:
        c_count = 0
        v_count = 0
        for i in ans:
            if i in 'aeiou':
                v_count += 1
            else:
                c_count += 1

        if v_count >= 1 and c_count >= 2:
            print(''.join(ans))

    else:
        for j in range(length, c):
            if ans and ans[-1] >= alphabet[j]:
                continue
            backtacking(length+1, ans+[alphabet[j]])

backtacking(0,[])

 

결과

---

예전에 풀었던 n과 m의 방식으로 문제를 풀었는데 자음과 모음의 갯수의 조건은 넣지 않았는데 시간초과가 되었다. 아무래도 모든 리스트를 만들기 때문이었던 것 같았고 풀 수 있는 방법을 모르겠어서 찾아봤다. 똑같이 백트래킹으로 구현했지만 조금은 다른 부분이 있어서 이해하고 풀어봤다. 모든 리스트 만드는 것 아직도 어렵긴 하지만 계속 보며 조금은 더 익숙해 진 것 같다.