길이가 짝수인 문자열 s가 주어졌다고 가정해 보겠습니다. 이 문자열을 길이가 동일한 두 부분으로 나누어야 하며, 앞쪽 절반을 a, 뒤쪽 절반을 b라고 부르겠습니다. 두 문자열이 포함하고 있는 모음(vowel)의 개수가 대소문자 구분 없이 서로 같다면, 우리는 이 두 문자열을 "유사하다(alike)"고 정의합니다. 즉, 이 문제의 목표는 a와 b가 유사한지 여부를 판별하는 것입니다.
예를 들어 입력이 s = "talent"라면 출력은 True입니다. 문자열을 나누면 "tal"과 "ent"가 되는데, 두 문자열 모두 모음이 하나씩, 자음이 두 개씩 포함되어 있어 서로 유사하기 때문입니다.
해결 접근 방법
이 문제는 다음과 같은 단계를 따라 해결할 수 있습니다.
a:= 문자열s의 왼쪽 절반b:= 문자열s의 오른쪽 절반count1:= 0,count2:= 0 으로 초기화a의 각 문자c에 대해 반복하며,c가 모음이면count1을 1 증가b의 각 문자c에 대해 반복하며,c가 모음이면count2를 1 증가count1과count2가 같으면true를 반환하고, 그렇지 않으면false를 반환
Python 예제 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
def solve(s):
vowels = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
a = s[:len(s)//2]
b = s[len(s)//2:]
count1 = 0
count2 = 0
for c in a:
if c in vowels:
count1 += 1
for c in b:
if c in vowels:
count2 += 1
return count1 == count2
s = "talent"
print(solve(s))
입력
"talent"
출력
True
더 간결한 대안 코드
파이썬의 제너레이터 표현식과 내장 함수 sum()을 활용하면 위 로직을 훨씬 간결하게 작성할 수도 있습니다.
def solve(s):
vowels = set('aeiouAEIOU')
mid = len(s) // 2
return sum(c in vowels for c in s[:mid]) == sum(c in vowels for c in s[mid:])
여기서 vowels를 집합(set)으로 선언하면 리스트보다 멤버십 검사 속도가 빨라진다는 장점도 있습니다.
시간 복잡도 분석
두 방식 모두 문자열의 각 문자를 한 번씩만 확인하므로 시간 복잡도는 O(n), 추가로 사용하는 공간은 상수 수준이므로 공간 복잡도는 O(1)입니다. 따라서 문자열의 길이가 커져도 효율적으로 동작합니다.