올바른 괄호 문제 (카탈란수 사용하지 않음)

카탈란수를 사용하지 않고 Stack 자료구조를 직접 구현합니다.

문제

올바른 괄호란 두 개의 괄호 '(' 와 ')' 만으로 구성되어 있고, 괄호가 올바르게 짝지어진 문자열입니다. 괄호가 올바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 합니다.
예를들어

()() 또는 (())() 는 올바른 괄호입니다.

---

풀이

1. 주어진 괄호 문자열의 첫번째 문자부터 마지막 문자까지 순서대로 리스트에 삽입합니다.

2. 리스트의 마지막 두 원소 문자열이 "(", ")" 인지 검사합니다. (리스트의 길이가 2 이상 일때)

3. 맞다면 마지막 두 원소를 리스트에서 제거합니다.

4. 작업을 마친 리스트의 길이가 0 이면 올바른 괄호입니다.

import java.util.ArrayList;

public class Hello {
    public static void main(String[] args) {
        // 주어진 괄호 문자열
        String str = "()()(((())))()()((()))";
        ArrayList<String> list = new ArrayList<>();

        // 괄호 길이만큼 순회
        for (int i = 0; i < str.length(); i++) {
            // 첫번째 괄호를 리스트에 집어넣기
            Add(str.substring(i, i + 1), list);
        }

        // 결과 확인
        boolean result = list.size() == 0;
        System.out.println("올바른 괄호? " + result);
    }

    // 리스트에 문자열을 더하는 함수 정의
    public static void Add(String _s, ArrayList _list) {
        _list.add(_s);
        // 리스트의 길이가 2 이상부터 완전한 괄호인지 검사
        if (_list.size() > 1 && Check(_list)) {
            // 만약 괄호가 완전히 닫아졌다면 마지막 두 원소를 제거
            _list.remove(_list.size() - 1);
            _list.remove(_list.size() - 1);
        }
    }

    // 리스트의 마지막 두 원소가 "()" 인지 확인
    public static boolean Check(ArrayList _list) {
        if (_list.get(_list.size() - 2).equals("(") && _list.get(_list.size() - 1).equals(")")) {
            return true;
        } else {
            return false;
        }
    }
}

> java Hello
올바른 괄호? true