📖Problem

🔍Intuition

짝을 찾아야 한다? 그러면 스택이 답이다.

그래서 이 문제는 스택이겠구나 싶었다.

(하지만 처음 접근할 때는 맨날 DP풀다가 오랜만에 스택 문제를 접해서, 다른 길로 샜다…)

(그래서 다른 길로 세서 잘못 시간초과가 나왔던 코드와, 스택으로 접근한 코드 모두 기록했다.)

스택으로 접근하려면 2가지를 고려해야 한다.

1. 언제 push할 것인가?
2. 언제 pop할 것인가?

1. 언제 push할 것인가?

   ⇒ pop하지 않을 경우에는 모두 추가한다.

   또는 stack에 아무것도 없다면 추가한다. (왜냐하면, 초기에 아무것도 없는데 pop해버리면 indexError가 발생하기 때문에 stack이 비어있을 경우에 추가하는 조건문을 넣어둬야 한다)

2. 언제 pop할 것인가?

   ⇒ 이건 쉽다. stack의 top과 현재위치에 해당하는 문자가 같으면 pop한다.

여기서 하나 더 고려해야 한다. 언제 반복을 종료할것인가?

⇒ 주어진 문자열 s를 다 보고 나면 종료해야 한다. 즉, for문을 쓰면 된다.

🔍Approach

접근: 스택