문제 설명
두 개의 소문자 문자열 s와 t가 있다고 가정해 봅시다. 사람이 키보드로 이름을 입력할 때, 가끔 모음 키를 실수로 오래 누르게 되어 해당 모음이 한 번 이상 반복되어 입력되는 경우가 있습니다. 우리가 확인해야 할 것은 문자열 t가 문자열 s를 타이핑한 결과일 가능성이 있는지 여부입니다.
예를 들어, s = "mine", t = "miiine"인 경우를 생각해 보겠습니다. 이때 출력은 True입니다. 왜냐하면 모음 'i'가 세 번 반복되었고(키를 오래 누른 것), 나머지 문자들은 정상적으로 입력되었기 때문입니다.
접근 방법 및 알고리즘
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- s_len := 문자열 s의 길이
- t_len := 문자열 t의 길이
- j := 0 (문자열 t를 가리키는 포인터)
- i를 0부터 s_len - 1까지 반복합니다.
- s[i]와 t[j]가 다르면 False를 반환합니다.
- s[i]가 모음이 아니라면 j를 1 증가시키고 다음 반복으로 넘어갑니다.
- cnt_1 := 1로 초기화한 후, s에서 연속된 같은 문자의 개수를 셉니다.
- cnt_2 := 1로 초기화한 후, t에서 해당 문자가 연속으로 나타나는 개수를 셉니다.
- 만약 cnt_1 > cnt_2라면 False를 반환합니다. (s에 있는 문자보다 t에 더 적게 반복될 수는 없기 때문입니다.)
- 모든 검사를 통과하면 True를 반환합니다.
핵심 아이디어는 자음은 정확히 한 번씩만 입력되어야 하지만, 모음은 키가 길게 눌려 여러 번 반복될 수 있다는 점입니다. 따라서 각 문자 그룹별로 s와 t에서의 반복 횟수를 비교하여, t의 반복 횟수가 s보다 작거나 같은지만 확인하면 됩니다.
예제 코드
아래 구현을 통해 더 잘 이해할 수 있습니다.
def isVowel(c):
vowel = "aeiou"
return c in vowel
def solve(s, t):
s_len = len(s)
t_len = len(t)
j = 0
for i in range(s_len):
if s[i] != t[j]:
return False
if isVowel(s[i]) == False:
j = j + 1
continue
cnt_1 = 1
while i < s_len - 1 and (s[i] == s[i + 1]):
cnt_1 = cnt_1 + 1
i = i + 1
cnt_2 = 1
while j < t_len - 1 and t[j] == s[i]:
cnt_2 = cnt_2 + 1
j = j + 1
if cnt_1 > cnt_2:
return False
return True
s = "mine"
t = "miiine"
print(solve(s, t))입력
"mine", "miiine"
출력
True
마무리
이 알고리즘은 두 문자열을 한 번씩 순회하면서 진행하므로 시간 복잡도는 O(n)입니다. 여기서 n은 두 문자열 길이 중 큰 값입니다. 공간 복잡도 역시 추가 배열 없이 포인터와 카운터 변수만 사용하므로 O(1)로 매우 효율적입니다. 키보드 오타 감지, 사용자 입력 검증 등 실제 상황에서도 응용할 수 있는 유용한 패턴 매칭 문제입니다.