[Python/파이썬] 백준 2922번 즐거운 단어

2922번: 즐거운 단어

 

문제

상근이는 자신이 다니는 학교에서 영어단어를 가장 많이 외우고 있다. 그 비법은 바로 조기교육이었다. 상근이는 젖병을 물기도 전에 영어 단어를 외웠다. 따라서, 지금은 자리에 앉으면 사전을 만들 수 있을 정도로 많이 외우게 되었다.

더 이상 외울 단어가 없어진 상근이는 이제 단어를 만들기로 결심했다.

상근이는 단어는 두 종류, 즐거운 단어와 즐겁지 않은 단어로 분류할 수 있다고 생각한다. 새로운 단어를 만들기 위해 즐겁지 않은 단어를 공책에 적는다. 그 다음, 보기 싫은 알파벳을 지우개로 지우고 그 자리에 밑 줄(_)을 적는다. 이렇게 보기 싫은 단어를 모두 지운 다음에는 즐거운 단어를 만들 수 있도록 밑 줄에 알파벳을 적는다.

상근이에게 즐거운 단어란, 모음(A,E,I,O,U)이 연속해서 3번, 자음(모음을 제외한 나머지 알파벳)이 연속해서 3번 나오지 않아야 한다. 또, L을 반드시 포함해야 한다.

상근이게 보기 싫은 알파벳을 지운 단어가 주어졌을 때, 즐거운 단어를 만들 수 있는 경우의 수를 세는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 공책에 적은 단어가 주어진다. 단어의 길이는 최대 100이고, 알파벳 대문자와 밑 줄(_)로만 이루어져 있다. 단어에 포함된 밑 줄의 개수는 최대 10이다.

출력

첫째 줄에, 밑 줄을 알파벳으로 바꿔 즐거운 단어를 만들 수 있는 경우의 수를 출력한다.

코드

word = input()

ans = 0


def vowel(c):
    if c in ['A', 'E', 'I', 'O', 'U']:
        return True
    return False


def bt(idx, word, nums):
    global ans
    if idx == len(word):
        # L을 포함하는 즐거운 단어인 경우
        if 'L' in word:
            ans += (5**nums[0])*(20**nums[1])
        return
    # word[idx]가 '_'인 경우
    if word[idx] == '_':
        # 모음
        if idx < 2 or not (vowel(word[idx-2]) and vowel(word[idx-1])):
            new_word = word[:idx]+'A'+word[idx+1:]
            bt(idx+1, new_word, [nums[0]+1, nums[1]])
        # 자음
        if idx < 2 or (vowel(word[idx-2]) or vowel(word[idx-1])):
            new_word = word[:idx]+'B'+word[idx+1:]
            bt(idx+1, new_word, [nums[0], nums[1]+1])
        # L
        if idx < 2 or (vowel(word[idx-2]) or vowel(word[idx-1])):
            new_word = word[:idx]+'L'+word[idx+1:]
            bt(idx+1, new_word, nums)
    else:
        # idx까지의 문자열이 모음 또는 자음이 3번 반복되지는 않는지
        if idx >= 2:
            if vowel(word[idx-2]) and vowel(word[idx-1]) and vowel(word[idx]):
                return
            if not (vowel(word[idx-2]) or vowel(word[idx-1]) or vowel(word[idx])):
                return
        bt(idx+1, word, nums)


bt(0, word, [0, 0])
print(ans)

백트래킹을 이용하여 가능한 모든 경우의 수를 세볼 것이다.

bt() 함수의 파라미터로 들어가는 idx는 word의 인덱스, nums는 밑줄을 채우는데 사용된 모음과 L을 제외한 자음의 개수이다.

• word[idx]가 '_'인 경우: word[idx] 자리에 자음, 모음, 'L'을 넣는 경우로 나누어서 bt 함수를 재귀호출한다. 이때, 모음이나 자음이 3번 중복되지 않는 경우에만 호출한다.
• word[idx]가 알파벳인 경우: idx-2에서 idx까지 모음이나 자음이 3번 이상 연속해서 반복되는 경우는 더이상 살펴볼 이유가 없으므로 이런 경우에는 리턴한다.