[LeetCode/Easy] 1047. Remove All Adjacent Duplicates In String

1. Input

1) String s

 

2. Output

1) 다음과 같은 규칙으로 문자열을 지워나갈 때, 최종 문자열을 반환

- 인접한 2개의 문자가 같으면 지운다.

- 더이상 지울 문자가 없을 때까지 반복한다.

 

3. Constraint

1) 1 <= s.length <= 10^5

2) s는 영어 소문자로만 이루어져 있다.

 

4. Example

Input: s = "abbaca" -> Output: "ca"

Input: s = "azxxzy" -> Output: "ay"

 

5. Code

1) 첫 코드(2023/04/04)

for(int i=0 ; i<s.length()-1 ; i++){
    if(s.charAt(i)==s.charAt(i+1)){
        s = s.substring(0,i) + s.substring(i+2,s.length());
        i = Math.max(-1,i-2);
    }
}
return s;

- 느리다. 메모리는 그럭저럭

2) 스택으로 구현해본 코드(2023/04/04)

Stack<Character> st = new Stack<>();
for(int i=0 ; i<s.length() ; i++){
    char c = s.charAt(i);
    if(!st.empty() && st.peek()==c)
        st.pop();
    else
        st.push(c);
}
s = "";
while(!st.empty())
    s += st.pop();
return new StringBuffer(s).reverse().toString();

- 1번보다 약간 빨라짐. 메모리는 더 먹음