카탈란수를 사용하지 않고
Stack
자료구조를 직접 구현합니다.
문제
올바른 괄호란 두 개의 괄호 '(' 와 ')' 만으로 구성되어 있고, 괄호가 올바르게 짝지어진 문자열입니다. 괄호가 올바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 합니다.
예를들어
()() 또는 (())() 는 올바른 괄호입니다.
풀이
주어진 괄호 문자열의 첫번째 문자부터 마지막 문자까지 순서대로 리스트에 삽입합니다.
리스트의 마지막 두 원소 문자열이 "(", ")" 인지 검사합니다. (리스트의 길이가 2 이상 일때)
맞다면 마지막 두 원소를 리스트에서 제거합니다.
작업을 마친 리스트의 길이가 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