키보드로 이름을 입력하다 보면 실수로 특정 키를 오래 누르는 경우가 있습니다. 이럴 때 같은 문자가 하나 이상 추가로 입력되곤 하죠. 이번 글에서는 두 개의 문자열을 받아, 두 번째 문자열이 첫 번째 이름을 길게 눌러(long-pressed) 입력한 결과인지 확인하는 방법을 알아보겠습니다.
예를 들어 원래 이름이 "Amit"이고 입력된 문자열이 "Ammittt"라면, m과 t가 여러 번 반복되었으므로 길게 눌린 이름입니다. 반면 "Ammttt"는 중간에 문자 i가 빠져 있기 때문에 길게 눌린 이름이 아닙니다.
해결 접근 방법
두 포인터(two pointer) 기법을 사용하면 간단하게 해결할 수 있습니다. 다음 단계를 따릅니다.
- 포인터 j를 0으로 초기화합니다.
- i를 0부터 typed 문자열의 길이까지 1씩 증가시키며 순회합니다.
- j가 name의 길이보다 작고, name[j]와 typed[i]가 같다면 j를 1 증가시킵니다.
- 순회가 끝난 뒤 j가 name의 길이와 같으면 true, 그렇지 않으면 false를 반환합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isLongPressedName(string name, string typed) {
int j = 0;
for(int i = 0; i < typed.size(); i++){
if(j < name.size() && name[j] == typed[i])j++;
}
return j == name.size();
}
};
main(){
Solution ob;
string res = ob.isLongPressedName("Amit", "Ammittt") ? "true" :
"false";
cout << res;
}입력
"Amit" "Ammittt"
출력
true
복잡도 분석
입력 문자열 typed를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 저장 공간 없이 포인터 변수만 사용하므로 공간 복잡도는 O(1)입니다.