https://leetcode.com/problems/backspace-string-compare/

s와 r 두 문자열이 주어진다. #은 백스페이스를 의미한다. 메모장에 해당 문자열을 입력했을 때 입력 값이 같다면 true를 리턴하라.

1. 제한조건 확인하기

두 개의 해쉬가 반복되면 두 번 빽스페이스를 누른 것으로 한다

지울 문자가 없을 경우 빽스페이스와 똑같이 동작한다

둘다 공백인 문자열은 동일한 것으로 판단한다

대소문자를 구분한다

나의 답안

기본적인 로직

t[i] 와 s[i] 가 #(해쉬)이 아니면 push하고 #(해쉬)이면 stack의 마지막 항목을 pop 하는 식으로 로직을 짰다.

const backspaceCompare = function (s, t) {
  let answer = false;
  let split_s = s.split("");
  let split_t = t.split("");
  let stack1 = [];
  let stack2 = [];
  for (i = 0; i < split_s.length; i++) {
    if ((split_s[i], split_t[i] != "#")) {
      stack1.push(split_s[i]);
      stack2.push(split_t[i]);
    } else {
      stack1.pop();
      stack2.pop();
    }
  }
  let string_s = stack1.join("");
  let string_t = stack2.join("");
  console.log(string_s);
  console.log(string_t);
  if (string_s === string_t) answer = true;
  return answer;
};

let s = "xywrrmp";
let t = "xywrrmu#p";

console.log(backspaceCompare(s, t));

내 로직의 오류

세가지의 테스트 케이스는 통과했지만 통과 못한 케이스가 존재했다. 문제는 for문을 돌리는 범위에 있었다. 나는 배열 s의 길이를 범위로 잡았는데, 만약 t의 길이가 더 길면 끝까지 안 돌고 끝나버리기 때문에 서로 비교할 때 당연히 false가 나올 수 밖에 없다.

생각의 전환

이떤 식으로 풀어야할까 고민해봤다. 우선 각 string의 길이만큼은 모두 배열에 push가 돼야하는 것 같다. 내 머리로 생각할 수 있는 건 이 두 가지였다.
1. 정규식을 이용해서 #이 있다면 백스페이스로 모두 바꾼다?
2. for문으로 i번째에 #이 있다면 i-1번째와 i번째를 모두 배열에서 제거한다? => 하지만 배열에서의 중간 항목 삭제는 index가 한칸씩 당겨져야하기 때문에 시간복잡도면에서 비효율적이다.

솔루션

const string1 = "ab#z"
const string2 = "az#z"

const buildString = function(string) {
    const builtString = [];
    for(let p = 0; p < string.length; p++) {
        if(string[p] !== '#') {
            builtString.push(string[p]);
        } else {
            builtString.pop();
        }
    }
    
    return builtString;
}

var backspaceCompare = function(S, T) {
    const finalS = buildString(S);
    const finalT = buildString(T);
    
    if(finalS.length !== finalT.length) {
        return false
    } else {
        for(let p = 0; p < finalS.length; p++) {
            if(finalS[p] !== finalT[p]) {
                return false
            }
        }
    }
    
    return true;
};

console.log(backspaceCompare(string1, string2));

핵심은 buildString 이라는 함수이다. 문제에서 주어진 조건을 판별하여 string을 만드는 로직을 따로 분리하였다.
이걸 법정에서의 재판에 비유해보면 피고인 S와 T는 backspaceCompare라는 사건으로 법정에 서게 되었다. 그리고 backspaceCompare라는 사건은 buildString이라는 기존 판례를 참고 할 만한다. 검사는 buildString라는 판례를 참고해 S 와 T의 주장(arguments)에서 각각 finalS 와 finalT 라는 결론을 도출하고 그에 따른 형량을 구형한다. 검사의 이러한 구형은 판사에게 전달되고 판사는 검사가 도출한 결론을 검토하여 backSpaceCompare라는 법 테두리 안에서 규정된 내용을 바탕으로 최종 판결을 내린다.
검사는 비슷한 주장을 하는 피고인 S와 T의 주장에 대한 판단을 할 때 buildString이란 잣대 하나만 참고하면 된다.