문제 08) 올바른 괄호 - (Stack 문제)

https://school.programmers.co.kr/learn/courses/30/lessons/12909?language=java

프로그래머스

---

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

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

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

---

입출력의 예

s	answer
"()()"	true
"(())()"	true

---

아이디어

사실 이 문제는 스택을 사용하지 않고, 문자열과 count라는 정수형을 만들어 '(' 개수보다 ')' 개수가 많아지면 false를 반환. 그리고 맨 앞과 맨 뒤가 '(', ')' 가 오지 않으면 false를 반환하도록 하여 함수를 구현했다. 그래도 푼 문제이니 코드를 기록해두고 정답을 보겠다.

private static boolean solution(String s){
        // 맨 앞이 ')'거나 / 맨 뒤가 '('가 오면 안됨
        if(s.charAt(0) == ')' || s.charAt(s.length() - 1) == '(')
            return false;

        int count = 0;

        for(int i=0; i<s.length(); i++){
            if(s.charAt(i) == '(')
                count++;
            else
                count--;

            if(count < 0)
                return false;
        }
        return count == 0;
    }

---

정답 코드

보통 이런 짝 맞추기 문제는 스택을 사용하면 된다.

주목해야 할 내용은 닫힌 괄호가 임의 위치의 열린 괄호와 상쇄되는 것이 아니라, 닫힌 괄호가 나오기 바로 전의, 즉 가장 가까운(최근) 열린 괄호와 상쇄된다는 것이다.

 

가장 가까운(최근)이라는 키워드를 보고 스택을 떠올리는 감각이 필요하다.

1. 문자열을 앞에서 하나씩 보며 열린 괄호가 나오면 push
2. 닫힌 괄호가 나오면 pop 연산을 통해 문자열에서 열린 괄호, 닫힌 괄호 한 쌍을 상쇄
3. 1~2를 마지막 문자열까지 반복해 스택에 열린 괄호가 남아 있다면 짝이 맞지 않은 것, 괄호가 남아 있지 않다면 짝이 맞은 것

private static boolean solution2(String s){
        ArrayDeque<Character> stack = new ArrayDeque<>();

        char[] a = s.toCharArray();
        for(char c : a){
            if(c == '(')
                stack.push(c);
            else{
                if(stack.isEmpty() || stack.pop() == c)
                    return false;
            }
        }

        return stack.isEmpty();
    }

 

==> 가장 가까운 키워드가 나오면 Stack을 사용하자 !