[leetcode] Valid Parenthesis String

문제

• 문제 링크
• '(', ')', '*'로 이루어진 문자열 s가 주어진다. s가 valid 한지 구해야 한다. valid 하다는 건 아래 조건을 만족하는 경우이다.
  • '(' 이후에는 짝이 되는 ')'가 존재해야 한다.
  • ')' 이전에는 짝이 되는 '('가 존재해야 한다.
  • '*'은 '(' 또는 ')' 또는 빈 문자열로 취급될 수 있다.
• 제약 조건
  • 문자열 길이: 1 <= s.length <= 100

풀이

풀기 전

• '*'이 없으면 간단한 문제인데 '*'이 조커처럼 추가되면서 조금 더 생각이 필요한 문제가 됐다. '*'은 필요시 '(' 또는 ')'를 대체하거나 아무 것도 대체하지 않을 수 있다. 대체해야 하는 타이밍을 생각하면 아래와 같이 정리할 수 있다.
  • '('를 대체한다는 건 ')'에 대응되는 '('가 이전에 없었다는 의미이다. 그래서 ')'를 순회하고 있을 때 '*'을 '('로 대체하여 사용할 수 있다.
  • ')'를 대체한다는 건 '('에 대응되는 ')'가 이후에 없다는 의미이다. 이건 문자열에 대한 모든 탐색이 끝난 후에야 알 수 있는 정보다.
• 위에 정리한 내용에 따라 코드를 두 단계로 나눠서 작성해볼 수 있다.
  • ')'와 짝이 되는 '('를 없애주기. 만약 짝이 없다면 '*' 사용해서 없애주기.
    ex) *)()((** -> ....((**
  • 아직 남아있는 '('이 있다면 '*' 사용해서 없애주기.
    ex) ....((** -> ........

코드

class Solution {
    public boolean checkValidString(String s) {
        Stack<Integer> leftIdx = new Stack<>();
        Stack<Integer> starIdx = new Stack<>();

		// 1단계: 우선 ')'를 없애주는 작업이다.
        char[] chars = s.toCharArray();
        for (int i=0; i<chars.length; i++) {
            char ch = chars[i];

            if (ch == '(') {  // '(' 만나면 stack에 넣어준다.
                leftIdx.add(i);
            } else if (ch == '*') {  // '*' 만나면 stack에 넣어준다.
                starIdx.add(i);
            } else {  // ')' 만나면
                if (!leftIdx.isEmpty()) {  // 대응되는 '('가 있을 경우 스택에서 뺀 뒤 배열에서 지워준다.
                    chars[leftIdx.pop()] = '.';
                    chars[i] = '.';
                } else if (!starIdx.isEmpty()) {  // '('가 없으면 '*'로 지워준다.
                    chars[starIdx.pop()] = '.';
                    chars[i] = '.';
                } else {  // '('와 '*' 둘 다 없으면 invalid 하다.
                    return false;
                }
            }
        }
        
        // 2단계: 남은 '('를 없애주는 작업이다.
        while (!leftIdx.isEmpty()) {
        	// '*'가 없거나 '('가 '*' 보다 뒤에 있으면 invalid 하다.
            if (starIdx.isEmpty() || leftIdx.peek() > starIdx.peek())
                return false;

			// 대응되는 '('와 '*'를 뺀다.
            leftIdx.pop();
            starIdx.pop();
        }

        return true;
    }
}

푼 후

• 처음에는 좀 복잡했는데 단계로 나눠서 생각해보니 풀렸다. '*'이 사용되는 경우의 조건을 생각해보는 게 중요한 거 같다.
• 문자열을 한 번 순회하고 문자열만큼의 스택도 한 번 순회하므로 시간 복잡도는 O(s.length)이다. 문자열만큼의 스택을 사용하므로 공간 복잡도도 O(s.length)이다.