Python으로 편집기의 최종 텍스트 구하기: 백스페이스('<-') 처리 프로그램

편집기에 순서대로 입력된 문자를 담고 있는 문자열 s가 있다고 가정해 봅시다. 이때 기호 "<-"는 백스페이스(직전 글자 삭제)를 의미합니다. 우리가 구해야 할 것은 모든 입력이 끝난 후 편집기의 최종 상태, 즉 화면에 남아 있는 텍스트입니다.

예를 들어 입력이 s = "ilovepython<-<-ON"이라면 출력은 "ilovepythON"이 됩니다. "ilovepython"을 입력한 뒤 두 번의 백스페이스가 마지막 두 글자 "on"을 지웠고, 다시 "ON"을 입력했기 때문입니다.

접근 방법

이 문제는 스택과 유사한 방식으로 간단히 해결할 수 있습니다. 핵심은 '<' 바로 뒤에 '-'가 나올 때만 이를 하나의 백스페이스로 해석하고, 나머지 문자는 모두 일반 입력으로 취급하는 것입니다. 알고리즘은 다음과 같습니다.

• 결과를 저장할 빈 리스트 res를 생성합니다.
• 문자열 s의 각 문자 i에 대해 다음을 반복합니다.
  • i가 '-'이고 res의 마지막 문자가 '<'라면("<-"가 완성된 경우):
    • res에서 마지막 요소('<')를 제거합니다.
    • res가 비어 있지 않다면 마지막 요소를 한 번 더 제거하여 실제 글자 하나를 지웁니다.
  • 그 외의 경우에는 i를 res의 끝에 추가합니다.
• 마지막으로 res의 모든 요소를 이어 붙여 반환합니다.

아래 구현 예제를 통해 더 잘 이해해 보겠습니다.

구현 예제

class Solution:
    def solve(self, s):
        res = []
        for i in s:
            if i == '-' and res[-1] == '<':
                res.pop()
                if res:
                    res.pop()
            else:
                res.append(i)
        return "".join(res)

ob = Solution()
print(ob.solve("ilovepython<-<-ON"))

입력

"ilovepython<-<-ON"

출력

ilovepythON

동작 과정 단계별 살펴보기

1. 'i'부터 'n'까지 차례로 추가 → "ilovepython"
2. '<'가 추가됨 → "ilovepython<"
3. '-'가 등장하고 직전 문자가 '<'이므로, '<'를 제거한 뒤 'n'도 제거 → "ilovepytho"
4. 같은 과정이 한 번 더 반복됨 → "ilovepyth"
5. 'O', 'N'이 추가됨 → 최종 결과 "ilovepythON"

복잡도 분석

문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 결과를 저장하는 리스트가 사용되므로 공간 복잡도 역시 O(n)입니다.

주의 사항

위 구현은 문자열이 일반 문자로 시작한다고 가정합니다. 만약 문자열 맨 앞에서 '-'가 먼저 나오면 res가 비어 있는 상태에서 res[-1]에 접근하게 되어 인덱스 오류가 발생할 수 있습니다. 실무에서는 조건을 if i == '-' and res and res[-1] == '<'처럼 확인하거나, 문자열 시작 부분의 백스페이스를 무시하도록 예외 처리를 추가하면 더욱 안전하게 동작합니다.