[leetcode][678] Valid Parenthesis String

문제 : https://leetcode.com/problems/valid-parenthesis-string/

---

'(', ')', '*' 로 이루어진 문자열이 입력값으로 주어진다.

*은 '(', ')'가 될 수 있고 빈 문자도 될 수 있다. 

 * 가 특정 문자로 대체될 때, 괄호들의 쌍이 맞는 경우 유효한 문자열이라 한다.

입력 문자열이 유효한 문자열인지 판단해라. 

---

여는 괄호가 나오는 인덱스를 저장하는 스택 하나와

'*' 가 나오는 인덱스를 저장하는 deque 하나를 사용한다.

 

입력된 문자열을 앞에서부터 탐색하면서 스택과 deque를 채운다.

1. 탐색중인 문자가 * 인 경우 deque의 뒤에 현재 인덱스를 채운다.

2. 여는 괄호인 경우 스택에 현재 인덱스를 push 한다.

3. 닫는 괄호인 경우 

  3-1. 스택이 비어있지 않은 경우 : 닫는 괄호로 짝을 맞춘다. = 스택을 pop.

  3-2. 스택이 비어있는 경우 = 짝을 이루는 여는 괄호가 없다.

    3-2-1. deque가 비어있지 않는 경우 : * 하나를 여는 괄호로 대처한다. = deque의 앞을 pop. (왜 앞인지 이유는 이후에 설명) 

    3-2-2. deque가 빈 경우 : 짝이 맞는 여는 괄호를 구할 수 없음 = 유효한 문자열이 아니다.

 

위 과정을 거쳤을 때, stack에는 짝이 맞지 않은 여는괄호의 인덱스가 스택에 있고, deque에는 닫는 괄호와 짝을 이루고 남은 *의 인덱스가 있다.

이제 * 를 닫는 괄호로 대처하여 여는괄호와 짝을 이룰 수 있는지 체크한다.

여는 괄호와 짝을 이루기 위해서는 해당 여는 괄호의 인덱스보다 커야된다. (앞에 있을수록 인덱스가 작기 때문에 3-2-1에서 닫는괄호와 짝을 이루는 *는 앞에서부터 사용했다. 인덱스가 큰 * 는 최대한 아껴서 지금 사용하기 위함.)

stack 크기 보다 deque의 크기가 더 작다면 유효한 문자열이 아니다. (여는 괄호의 개수가 남기때문에)

 

스택을 pop 하면서 deque의 가장 뒤에있는 인덱스와 비교한다. 만약 deque 인덱스(닫는 괄호)가 stack의 top(여는 괄호)보다 크다면 이는 유효한 짝이다. 반대로 deque 인덱스가 stack의 top보다 작다면 여는 괄호와 짝을 이루는 * 이 없다는 뜻이므로 유효한 문자열이 아니게 된다. 

 

시간복잡도는 O(N). N = 문자열 길이.

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/678.%20Valid%20Parenthesis%20String.cpp