알고리즘 문제 풀이 #2 올바른 괄호

programers에서 문제 풀이한 내용입니다. 

문제 설명

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

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

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

제한사항

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

입출력 결과

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

문제 풀이 1

public boolean correctParentheses_1(String str) {
    boolean answer = true;

    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);

        // 여는 괄호일 때
        if (c == '(') {
            stack.push(c);
        }

        // 닫는 괄호일 때
        if (c == ')') {
            if (stack.size() > 0) {
                stack.pop();
            } else {
                return false;
            }
        }
    }

    if (stack.size() != 0) {
        answer = false;
    }
    return answer;
}

다른 사람 풀이 2

public boolean correctParentheses_2(String str) {
    boolean answer = true;

    int count = 0;

    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);

        if (c == '(') {
            count++;
        }
        if (c == ')') {
            count--;
        }
        if (count < 0) {
            answer = false;
        }
    }
    return answer;
}

배운 점: 문제에서 스택이라는 힌트를 줘서 Stack을 이용해서 풀이했지만, 다른 사람들의 풀이를 보니 그걸 안 쓰고도 충분히 풀 수 있는 문제였다. 힌트에 얽매이지 말고 근본적인 문제 해결을 해보도록 노력해 보자.