844. Backspace String Compare

목표

주어진 두 개의 문자열 명령 S와 T가 동일한 출력 값으로 나오는지 확인하는 판독기를 코딩하라.

문자열에서 '#'는 백스페이스 키에 해당된다.

예시 1

입력값: S = "가나#다", T = "가라#다"
출력값: true
설명: S와 T 둘 다 출력값이 "가다" 이므로 판독기는 true를 출력합니다.

예시 2

입력값: S = "가다##", T = "다#라#"
출력값: true
설명: S와 T 둘 다 출력값이 "" 이므로 판독기는 true를 출력합니다.

그냥 쓴 알고리즘

급하게 생각해본 알고리즘이다. 문자열이 변경 불가능한 객체이므로^[각주:1] (immutable) 문자열을 리스트(list)로 변경 후 직접 문자열을 인덱스 0부터 시작해 끝까지 확인하는 while 루프를 택했다.

보다시피 작동은 하긴 하지만, 쓸데없는 확인과정이 많은 알고리즘이다.

1. 일단 리스트 내에 '#'가 있는지 확인한다. 있으면 루프를 계속 돌린다.
2. 리스트 내 첫번째 '#'의 인덱스를 확인하고 인덱스가 0인지 아닌지 확인한다. 만약에 0이라면 다음 과정에서 pop 명령문이 인덱스 -1, 그러니까 리스트 맨 끝에 있는 문자열을 제거해버리는 버그가 발생할 것이다. 0 이면 '#' 만 제거한다.
3. '#'가 발견된 인덱스 앞에 있는 문자를 리스트에서 제거하고 '#'도 제거한다. 

해당 과정을 다시 T에 적용시키고 이걸 또 다시 쓸데없이 리스트에서 문자열로 통합시키고 비교시킨 참 거짓 값을 내놓도록 했다. 대략 112ms가 걸렸다.

while '#' in S:
 if S.index('#') != 0:
         S.pop(S.index('#')-1)
           S.remove('#')
     else:
           S.remove('#')
                
while '#' in T:
     if T.index('#') != 0:
           T.pop(T.index('#')-1)
           T.remove('#')
     else:
           T.remove('#')
            
S = "".join(S)
T = "".join(T)
        
if S == T:
  return True
else:
  return False
 

O(n) 알고리즘

좀 더 곰곰히 생각해보자. 알다시피 뭔가를 타이핑할 때 우리는 문장 처음부터 시작한다. 중간에 백스페이스 명령을 넣으면 제일 끝에 있는 문자부터 제거한다. 여기에서 우리는 뭔가 어디서 많이 본듯한 자료구조가 생각날 것이다. 그렇다. 스택이 떠올려진다. 정확히 말하자면 후입선출 Last In Last Out (LIFO) 구조다. 파이썬에서는 리스트로 스택 자료구조를 재현할 수 있다. 필자는 실험적으로 살짝 더 빠른 덱(deque)을 이용해 알고리즘을 구현했다.

보다시피 훨씬 간단하고 과정이 빠르다.

1. 일단 리스트 두 개를 정의한다. 스택처럼 사용한다.
2. 문자열을 쭉 내려가는 for 루프를 정의한다.
3. '#'를 발견하면 리스트 끝에 있는 문자를 떼어낸다. 리스트가 비어있으면 버그가 발생하므로 if로 일단 리스트가 비어있는지 확인한다. 만약 비어있으면 아무 것도 하지 않고 문자열의 다음 문자로 넘어간다. 만약 '#'가 아니라면 문자를 리스트에 추가(append)한다.
4. 2,3 과정을 T에 반복한 후 list1 과 list2를 비교한 참 거짓값을 출력한다.

20ms가 걸렸다. 덱을 사용하면 16ms가 걸린다.

list1 = []
list2 = []
for letter in S:
 if letter == '#':
      if list1:
         list1.pop()
   else:
      list1.append(letter)
        
for letter in T:
   if letter == '#':
      if list2:
         list2.pop()
   else:
      list2.append(letter)
        
      
return list1 == list2

[Copyright ⓒ 블로그채널 무단전재 및 재배포 금지]  

1. 해당 사항은 문자열에 있는 문자 중 하나를 직접 변경 해보는 시도를 하는 것으로 확인할 수 있다. 컴파일러가 거부할 것이다. [본문으로]