[프로그래머스] 옹알이 (2)(Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/133499

프로그래머스

소스 코드

import re
def solution(babbling):
    # 각 원소에 속한 발음 가능한 단어를 숫자로 치환
    for i in range(len(babbling)):
        babbling[i] = babbling[i].replace('aya','1')
        babbling[i] = babbling[i].replace('ye','2')
        babbling[i] = babbling[i].replace('woo','3')
        babbling[i] = babbling[i].replace('ma','4')

    cnt = 0
    # 각 단어마다 확인
    for babble in babbling:
        # 숫자가 아닌 문자가 남아 있는 경우
        if re.findall('[a-z]',babble): continue
        # 숫자만 남아있지만 연속된 숫자가 존재하는 경우
        elif '11' in babble or '22' in babble or '33' in babble or '44' in babble: continue
        # 숫자만 존재하며 연속된 숫자가 없는 경우
        else: cnt += 1
    return cnt

해설

• re 모듈을 이용한 문자 탐색
• 간단한 조건을 설정하는 단순 구현 문제

시간복잡도

babbling의 길이 n은 최대 100이므로 replace 함수를 쓸 때 O(N),

두 번째 for문도 마찬가지로 O(N)의 시간 복잡도를 가집니다.

 

구체적인 숫자를 보면 첫 번째 for문에서는 100 x 4 = 400(최대),

두 번째 for문에서는 100 x 6 = 600(대략, 최대)번 정도의 연산이 수행됩니다.

각 원소의 최대 길이는 30이므로 이를 포함시켜 계산하더라도 시간 복잡도에서 문제될 것은 없다는 걸 알 수 있습니다.

풀이

첫 번째 for문에서는 발음을 테스트 해 볼 단어 리스트에 포함된 단어 중, 발음 가능한 네 개의 단어가 포함되어 있다면 이를 숫자로 치환합니다.

예를 들어 babbling = ["ayaye", "uuu", "yeye", "yemawoo", "ayaayaa"]인 경우, 첫 번째 단어 "ayaye"는 "aya" + "ye"로 구성되어 있으므로 '12'로 바뀌게 될 것입니다.

이렇게 하는 이유는 발음 가능한 단어인지 아닌지를 판별할 때 해당 문자열이 오직 숫자로만 구성되어 있는지 확인하기 위함입니다.

 

두 번째 for문에서는 조건을 통해 숫자로만 구성된 단어이며 연속 발음되는 경우가 없는지 확인합니다.

따라서 1) 문자가 포함되어 있지 않고, 2) 연속된 숫자 조합이 없는, 모든 경우가 발음 가능한 단어입니다.

이때 1) 문자가 포함되어 있지 않는 경우를 코드로

if re.findall('[a-z]',babble): continue

이렇게 작성했습니다.

re 모듈에 포함된 findall 함수는 'findall( 조건식, 대상)'과 같은 형태로 사용하며,

위 문제에서는 'a부터 z까지'에 해당하는 문자가 babble에 포함되어 있는 모든 경우를 찾아주게 됩니다.

따라서 그러한 경우가 존재하여 true값이 반환되면 count하지 않습니다.