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

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

 

문제: www.acmicpc.net/problem/1759

 

내코드

 

• 이전 백트래킹 문제들과 푸는 방식은 비슷하지만 포인트는 크게 두가지 였다.
  1. 자음과 모음의 최소 포함 개수가 정해져 있었다는 것
  2. 사전 순으로 출력해야 한다는 것
• consonant_n, vowel_n 변수를 따로 선언해줘서 자음 모음 개수를 저장해주고 마지막에 개수를 확인해 준뒤 출력해줬다.
• 또한 out변수에 append하기 전에 out 리스트의 마지막 문자보다 현재 입력하려고 하는 문자가 사전순으로 뒤에 있는지 확인해 준뒤 입력해줬다.
• 문제를 풀면서 맞게 풀었다고 생각했는데 틀렸다고 나왔다. 처음 입력받은 문자열 리스트를 sorted()로 정렬해주니 해결되었다.

 

# BaekJoon1759.py 암호 만들기

l, c = map(int, input().split())
arr = sorted(input().split())
visited = [False] * c # 사용 여부 저장
vowel = ['a', 'e', 'i', 'o', 'u'] # 모음
consonant_n = 0 # 자음 개수
vowel_n = 0 # 모음 개수
out = [] # 출력 배열 저장


def solve(con, vow):
    if len(out) is l:
        # 최소 한개의 모음, 최소 두개의 자음으로 구성하기 위한 조건
        if con > 1 and vow > 0:
            print(''.join(map(str, out)))
        return
    else:
        for i in range(c):
            # 방문했다면 pass
            if visited[i]:
                continue
            # 사전순으로 구성하기 위한 조건
            if len(out) != 0 and out[-1] > arr[i]:
                continue
            # 방문했다고 표시
            visited[i] = True
            out.append(arr[i])
            # 모음, 자음 여부 기록
            if arr[i] in vowel:
                vow += 1
                # 다음 문자 정하기 위해
                solve(con, vow)
                vow -= 1
            else:
                con += 1
                solve(con, vow)
                con -= 1
            visited[i] = False
            out.pop()


solve(consonant_n, vowel_n)