Algorithm : 괄호 기호가 Valid한지 체크하기

Gatsby로 블로그 마이그레이션을 하여 이 링크를 클릭하면 해당 포스팅으로 갑니다. 

감사합니다. 

http://blog.advenoh.pe.kr

1. Problem

면접에서도 자주 나올 수 있는 문제중에 하나입니다. 여러 조합의 괄호 기호가 OPEN, CLOSE 매칭이 딱딱 맞아 떨어지는지 체크하는 문제입니다. 

public boolean solution(String str) {
...
}

1.1 입력 / 결과

입력 가능한 String 값은 아래와 같습니다. 

• ()()() —> true
• ((()))()() —> true

• )(  —> false

• ((())))) —> false 

2. Solution

2.1 Approach 1

이 문제를 쉽게 해결하는 방법은 스택 자료 구조를 이용하는 것입니다. 기본 아이디어는 다음과 같습니다. 

1. String의 한 char씩 스킨한다
2. OPEN_괄호 ‘(‘ 을 만나면 스택에 push한다
3. CLOSE_괄호 ‘)’를 만나면 스택에서 pop을 한다
4. 스택에 아무것도 남아 있지 않으면, valid한 괄호인것으로 판단할 수 있다

public boolean solution(String str) {
    char[] chars = str.toCharArray();
    Stack<Character> stack = new Stack<>();

    if (str.length() % 2 != 0) {
        return false;
    }

    if (chars[0] == ')') {
        return false;
    }

    for (char ch : chars) {
        if (ch == '(') {
            stack.push(ch);
        } else {
            // close parenthesis
            stack.pop();
        }
    }
    return stack.isEmpty();
}

소스코드는 github에서도 확인할 수 있습니다. 

이 문제에서는 소괄호 (, )만 사용했지만, 여러 괄호 { [ ( ) ] }가 더 있는 경우에도 여러 조합이 valid한지를 체크하는 코드로 더 문제를 키울 수 있을 것 같습니다. 기존 아이디어와 같이 스택을 사용하면 업그레이된 문제도 쉽게 해결하면 가능합니다. 이건 독자분들에게 남겨두도록 하겠습니다. 

• ({{}}(())) --> true
• ({}[[[]]{}) --> true

3. Reference

• https://hongku.tistory.com/251