2-7. Backspace String Compare (LeetCode 844)

---

문제 풀기 전 생각 : 

스택을 응용하면 쉽게 풀 수 있을거라고 생각했습니다.

주어지는 두 개의 string 을 인덱싱해서 스택에 하나씩 넣으며 

"#" 가 나타나면 top을 하나 감소시킵니다.

두 개의 스트링 모두 위의 작업이 끝나면 둘의 길이를 먼저 비교합니다. 

만약 다르다면 false를 리턴합니다.

다음으로 스택의 내용물을 비교합니다. 만약 다른게 있다면 false를 리턴하고

반복문이 무사히 종료된다면 true를 리턴합니다.

---

#include <iostream>
using namespace std;

class Solution {
public:
    bool backspaceCompare(string s, string t) {
        char s1[s.length()];
        char s2[t.length()];
        
        int top1=0,top2=0;
        
        for(int i = 0 ; i < s.length() ; i++){
            if(s[i] == '#') {
                if(top1 != 0) {
                    top1--;
                    s1[top1] = '\0';
                }
            }
            else {
                s1[top1] = s[i];
                top1++;
            }
        }
        for(int i = 0 ; i < t.length() ; i++){
            if(t[i] == '#') {
                if(top2 != 0) {
                    top2--;
                    s2[top2] = '\0';
                }
            }
            else {
                s2[top2] = t[i];
                top2++;
            }
        }
        if(top1 != top2) return false;
        for(int i=0 ; i<top1 ; i++){
            if(s1[i] != s2[i]) return false;
        }
        
        return true;
    }
};

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

Backspace String Compare - LeetCode

---

풀 때 어려웠던 점 또는 느낀점 :

생각했던 대로 코드를 짠 후 테스트 케이스를 통과해 한번에 풀었다고 생각해 기뻐했지만

top를 하나 감속시키만 한다면 '#'로 끝나는 string에서는 더미 값이 그대로 남아있어

원하는 결과값이 나오지 않았습니다. 인덱싱으로 배열을 스택처럼 사용했기 때문에 고려해야 하는 부분이었습니다. 

그래서 '#'가 나왔을 때 top을 감소시킨 후 top에 해당하는 값을 '\0'로 바꿔주니 결과값이 올바르게 나오게 되었습니다.