[백준 2922] 즐거운 단어 (Python)

 

www.acmicpc.net/problem/2922

2922번: 즐거운 단어

 

문제풀이

mo : 모음

ja : 자음

S : 입력값

 

go(s, idx, ch) : 재귀적으로 _에 문자를 놓는 함수, s : 문자열, idx : 인덱스, ch : _에 지금까지 사용한 단어

verify(s) : s가 문제의 조건(자음, 모음 연속 3개인지 아닌지, s에 L이 포함되어 있는지)에 위배하지 않는지 확인

 

_ 에 들어올 수 있는 글자는 모음, L이 아닌 자음, L 총 3가지 가능 => 3^10 이므로 브루트포스로 해결 가능하다
모음을 사용한 경우에는 A를 사용하여 총 모음의 개수(5개)만큼 곱해준다.
L이 아닌 자음을 사용한 경우는 B를 사용하여 총 자음의 개수(L 제외 20개)만큼 곱해준다.
L을 사용한 경우는 L을 사용하여 1 만큼 곱해준다.

 

1. 문자열 S의 가장 첫 인덱스로부터 처음 만나는 _ 에서 재귀를 시작한다.

 

2. go 함수의 문자열 s에서 _가 없는지 확인한다. => _가 없으면 _를 특정 문자로 전부 채운 경우이다.

- 문자열 s가 문제의 조건에 위배되지 않는지 검증한다.

- 지금까지 _에서 사용한 문자(모음 : A 사용, L 제외 자음:  B사용, L : L사용)에 따라 tmp에 값을 곱해준다. (L 제외 자음 : 20 모음 : 5 L: 1)

- ans와 tmp를 더해준다.

 

3. 문자열에서 재귀를 이용해 _ 만큼 문자를 사용한다.

- 모음의 경우 'A' 사용

- L이 아닌 자음의 경우 'B'사용

- L의 경우 'L' 사용

 

4. 결과(ans)를 출력한다.

 

 

코드

# _ 에 들어올 수 있는 글자는 모음, L이 아닌 자음, L 총 3가지 가능 => 3^10 이므로 브루트포스로 해결 가능
# 모음을 사용한 경우는 A 사용
# 자음을 사용한 경우는 B 사용
# L을 사용한 경우는 L 사용

def verify(s):
    mo = ['A', 'E', 'I', 'O', 'U'] # 모음
    ja = ['B', 'C', 'D', 'F', 'G', 'H', 'J', 'K', 'L', 'M', 'N', 'P', 'Q', 'R', 'S', 'T', 'V', 'W', 'X', 'Y', 'Z'] # 자음
    if 'L' not in s: return False # L이 없으면 false
    for i in range(len(s) - 2):
        if s[i] in mo and s[i + 1] in mo and s[i + 2] in mo: return False # 모음 3개 연속인 경우 false
        if s[i] in ja and s[i + 1] in ja and s[i + 2] in ja: return False # 자음 3개 연속인 경우 false
    return True

def go(s, idx, ch): # 문자열 s, 인덱스 idx, 사용한 단어 ch
    global ans
    if '_' not in s: # S에 _가 없는 경우
        if verify(s): # 문자열 s 검증
            tmp = 1
            for y in ch: # 사용한 단어 확인
                if y == 'A': tmp *= 5 # 모음을 사용한 경우 5가지
                elif y == 'B': tmp *= 20 # L이 아닌 자음을 사용한 경우 20가지
                else: tmp *= 1 # L을 사용한 경우 1가지
            ans += tmp
        return
    for i in range(idx, len(s)):
        if s[i] == '_':
            s = s[:i] + 'A' + s[i + 1:] # 모음 사용
            go(s, idx + 1, ch + 'A')
            s = s[:i] + 'B' + s[i + 1:] # L이 아닌 자음 사용
            go(s, idx + 1, ch + 'B')
            s = s[:i] + 'L' + s[i + 1:] # L 사용
            go(s, idx + 1, ch + 'L')
            return

if __name__ == '__main__':
    S = input()
    flag = False
    ans = 0
    for i in range(len(S)):
        if S[i] == '_': # S에서 처음으로 _ 발견하면 그때부터 재귀 시작
            flag = True
            go(S, i, '')
            break
    if not flag: ans = 1 # S에서 _가 한개도 없는 경우
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!