[프로그래머스] 올바른 괄호

문제 설명

괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’ 문자로 닫혀야 한다는 뜻입니다. 예를 들어

• ”()()” 또는 “(())()” 는 올바른 괄호입니다.
• ”)()(“ 또는 “(()(“ 는 올바르지 않은 괄호입니다.

’(‘ 또는 ‘)’ 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한 사항

• 문자열 s의 길이 : 100,000 이하의 자연수
• 문자열 s는 ‘(‘ 또는 ‘)’ 로만 이루어져 있습니다.

프로세스

짝을 짓는 데 단순하게 열린 괄호의 개수와 닫힌 괄호의 개수를 구하고 그 수가 맞는 지를 볼 수도 있겠지만, 당장 “)(“ 이 경우는 어떻게 할 지가 막막할 것이다.

우리가 괄호가 완전하다 하는 것은 열린 괄호가 나온 후에 닫힌 괄호가 나와야 하는 것이고, 중첩 괄호의 경우, 안쪽부터(깊이가 가장 깊은 것) 닫혀야 한다.

따라서 스택을 이용하여 열린 괄호가 나오면 스택에 push하고, 닫힌 괄호가 나오면 바로 이전에 들어간(같은 깊이의 열린 괄호) 것부터 pop하여 해당 괄호가 닫혔음을 나타냈다.

주어진 문자열을 모두 탐색했을 때, 스택이 비어있지 않다면, 괄호가 닫히지 않았음을 의미하기 때문에 false를 반환했다.

코드

import java.util.*;

class Solution {
    boolean solution(String s) {
        if (s.length() == 1) // 빈 문자열이거나 괄호가 한 쪽만 있는 경우
            return false;
        
        char[] cArray = s.toCharArray();
        Stack<Character> stack = new Stack<Character>();
        stack.push(cArray[0]); // 초기 스택 세팅
        
        for (int i = 1; i < cArray.length; i++) {
            if (cArray[i] == ')') {
                if (stack.isEmpty()) // 앞에 열린 괄호가 없이 닫힌 괄호가 나오는 경우
                    return false;
                stack.pop();
            }
            else
                stack.push(cArray[i]);
        }
        
        if (!stack.isEmpty())
            return false;
        return true;
    }
}

앞선 제한사항에 문자열 길이가 100,000 이하의 자연수라 했으므로, 길이가 1인 문자열이 들어올 수 있다.
따라서 그런 경우엔 바로 false를 반환하도록 했다.

만약 닫힌 괄호가 나오려 할 때 앞서 열린 괄호가 없다면, 이 괄호 또한 완전한 괄호가 아니므로 바로 false를 반환한다.