LeetCode 3330 문제 풀이: "Find the Original Typed String I"

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

바이브코딩

대상자

• 초보 개발자 및 알고리즘 문제 풀이자
• 난이도: 중간 (문자열 순회 및 간단한 조건 처리 기술 필요)

핵심 요약

• 문제 핵심: 반복된 문자열 그룹에서 최대 하나의 추가 문자를 삭제한 경우의 가능한 원본 문자열 수 계산
• 알고리즘: O(n) 시간 복잡도로 연속된 중복 문자만 검사하여 카운트
• 코드 예시:

```cpp

if (word[i] == word[i - 1]) ++ans;

```

```python

if word[i] == word[i - 1]: ans += 1

```

```javascript

if (word[i] === word[i - 1]) ans++;

```

섹션별 세부 요약

1. 문제 설명

• 입력: 중복 문자가 하나 포함된 최종 문자열 word
• 출력: 원본 문자열의 가능한 경우의 수
• 예시: "aab" → "aab", "ab" (1개의 중복 문자 삭제)

2. 접근 방법

• 초기 조건: ans = 1 (입력 문자열 자체가 하나의 경우)
• 문자열 순회: 두 번째 문자부터 시작하여 연속된 중복 문자를 확인
• 카운트 증가: 중복 문자가 발견될 때마다 ans 증가

3. 코드 구현

• C++: for 루프로 반복, word[i] == word[i - 1] 조건 적용
• Python: range(1, len(word))로 순회, 동일 조건 활용
• JavaScript: for 루프와 === 연산자로 중복 문자 비교

4. 시간/공간 복잡도

• 시간 복잡도: O(n) (문자열 길이 n에 비례)
• 공간 복잡도: O(1) (추가 메모리 사용 없음)

결론

• 핵심 팁: 연속된 중복 문자만 고려하고, 하나의 추가 문자 삭제 가능성을 기반으로 카운트
• 실무 적용: 간단한 문자열 처리 알고리즘 설계 시, 선형 시간 복잡도를 유지하면서도 효율적인 해결이 가능
• 예시: "aaa" → "aaa"(기본), "aa"(1번 삭제), "a"(2번 삭제) → 총 3가지 가능 → ans = 3