문제
머쓱이는 태어난 지 6개월 된 조카를 돌보고 있습니다. 조카는 아직 "aya", "ye", "woo", "ma" 네 가지 발음을 최대 한 번씩 사용해 조합한(이어붙인) 발음밖에 하지 못합니다. 문자열 배열 babbling이 매개변수로 주어질 때, 머쓱이의 조카가 발음할 수 있는 단어의 개수를 return하도록 solution 함수를 완성해 주세요
제한사항
- 1 <=
babbling의 길이 <= 100 - 1 <=
babbling[i]의 길이 <= 15 babbling의 각 문자열에서 "aya", "ye", "woo", "ma"가 한 번씩만 등장합니다.
* 즉, 각 문자열의 가능한 모든 부분 문자열 중에서 "aya", "ye", "woo", "ma"가 한 번씩만 등장합니다.- 문자열은 알파벳 소문자로만 이루어져 있습니다.
입출력 예
| babbling | result |
|---|---|
| ["aya", "yee", "u", "maa", "wyeoo"] | 1 |
| ["ayaye", "uuuma", "ye", "yemawoo", "ayaa"] | 3 |
입출력 예 설명
입출력 예 # 1
- ["aya", "yee", "u", "maa", "wyeoo"]에서 발음할 수 있는 것은 "aya"뿐입니다. 따라서 1을 return합니다.
입출력 예 #2
- ["ayaye", "uuuma", "ye", "yemawoo", "ayaa"]에서 발음할 수 있는 것은 "aya" + "ye" = "ayaye", "ye", "ye" + "ma" + "woo" = "yemawoo"로 3개입니다. 따라서 3을 return합니다.
유의사항
- 네 가지를 붙여 만들 수 있는 발음 이외에는 어떤 발음도 할 수 없는 것으로 규정합니다. 예를 들어 "woowo"는 "woo"는 발음할 수 있지만 "wo"를 발음할 수 없기 때문에 할 수 없는 발음입니다.
문제 특징
- 각각 한 번씩만 사용 가능하므로 네 단어들로만 이루어져있으며 중복 없이 구성되어야 함
사고 흐름
- 문자열 안에 제한된 단어만 허용 : 부분 문자열 검사 (in) or replace
- 중복 사용 금지 : 사용 횟수 추적 또는 replace 후 검증
- 이어붙인 형태만 허용 : 완전히 치환 후 빈 문자열인지 확인
접근 방식
- 방법 1 : 문자열 치환 + 검증
1. "aya", "ye", "woo", "ma"를 하나씩 replace()로 제거
2. 모든 단어를 제거한 뒤 남은 문자열이 ""이면 → 유효한 단어
3. 단, "ayaaya"처럼 같은 단어 두 번 쓰면 제거되긴 해도 유효하지 않음 → 이를 검출해야 함 - 방법 2 : 정규 표현식 (정규식) 사용
• '^(aya|ye|woo|ma){1,4}$' 패턴과 일치하는 문자열만 허용
• 단, 중복 단어 방지는 추가 로직 필요함
알고리즘
- 문자열 처리
- Set 활용
- 정규 표현식
시간 복잡도
babbling의 길이를 n, 각 문자열의 최대 길이를 l이라고 할 때, 전체 시간복잡도는 O(n × l)
(방법 3 : O(k)(k < l, k는 실제로 검사하게 되는 평균적인 문자 수))
코드
방법 1: 문자열 치환(replace) + 중복 방지
def solution(babbling):
valid = ["aya", "ye", "woo", "ma"]
count = 0
for word in babbling:
temp = word
for v in valid:
temp = temp.replace(v, " ")
# 중복 방지를 위해 한 단어가 두 번 연속 사용된 경우 제거
if all(word.count(v*2) == 0 for v in valid) and temp.strip() == "":
count += 1
return count방법 2: 정규 표현식 (re 모듈) + 중복 방지
import re
def solution(babbling):
valid = ["aya", "ye", "woo", "ma"]
count = 0
for word in babbling:
# 정규식으로 전체가 valid 단어들로만 구성되어 있는지 확인
if re.fullmatch(r"(aya|ye|woo|ma)+", word):
# 중복 단어 사용 방지
is_duplicate = any(v * 2 in word for v in valid)
if not is_duplicate:
count += 1
return count방법 3: 시간복잡도 개선 (replace 방식 기반)
def solution(babbling):
valid = ["aya", "ye", "woo", "ma"]
count = 0
for word in babbling:
# 1. 길이 초과 시 즉시 탈락
if len(word) > 10:
continue
# 2. 중복된 단어가 연속된 경우 탈락
if any(v*2 in word for v in valid):
continue
# 3. 유효 단어만 replace하고 나머지 문자가 남으면 탈락
temp = word
for v in valid:
temp = temp.replace(v, " ")
if temp.strip() == "":
count += 1
return count