Remove Adjacent Duplicates

• Reference
• 중복되는 문자를 지워주는 문제다.
• Stack Approach가 얼마나 중요한지 알려주는 문제였다.

Algorithm

abbcddde

• 기초적으로는 중복되는 2문자가 있으면 지워주는 문제를 생각해본다.

 -> top : null, push : a
 a -> top : a, push : b
 ab -> top : b, pop : b
 a -> top : a, push : c
 ac -> top : c, push : d
 acd -> top : d, pop : d ...

• 위와 같은 식으로 top과 현재 push 하고자하는 변수를 통해 stack에 push 할지, pop을 할지를 정하면 된다.

• 좀 더 난이도가 올라가면 k=2, k=3, k=4 형식으로 중복되는 문자의 개수를 지정해주기도 한다.

• k = 3 인 경우를 생각해보자.

  -> top : null, push : a
  a -> top : a, push : b
  ab -> top : b, push : b ??

• 2개인지 3개인지 어떻게 알까? 이전 min/max stack 처럼 하나의 stack 같은 memory를 사용한다.

  -> top : null, push : a
  (stack2) push 1 (a의 개수를 세는 것이다.)
  a -> top : a, push : b
  (stack2) push 1 (b의 개수를 세는 것이다.)
  ab -> top : b, push : b
  (stack2) top update 1 -> 2 (b의 개수를 세는 것이다.)
  abb -> top : b, push : c
  (stack2) push 1
  abbc -> top : c, push : d
  (stack2) push 1
  abbcd -> top : d, push : d
  (stack2) top update 1 -> 2 (d의 개수를 세는 것이다.)
  abbcdd -> top : d, pop : d
  (stack2) top update 2 -> 3 ==> stack2의 top을 pop하여 해당 count 만큼 pop 수행