올바른 괄호
문제설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 함수를 완성해 주세요.
Main Method
public static void main(String[] args) {
String s = ")()(";
boolean answer;
answer = isMate(s);
System.out.println(answer);
}애초에 문제 카테고리가 스택 or 큐를 이용하는 문제로 분류가 되어있었다.
문제를 보자마자 그냥 스택에 넣고 열린괄호, 닫힌괄호 갯수가 맞으면 true 반환하는
그저 그런 문제로 생각했는데, 문제를 제대로 이해하지 못하고 열린괄호로 열려서
닫힌괄호로 닫혀야 한다는 조건도 있는것을 보지 못했다.
그래서 처음에 푸시하는 반복문과 팝하는 반복문을 작성하고 int형 변수를 증감시켜서 0일 경우 반환했는데, 아니나 다를까 테스트 케이스에서 대부분 실패하였다.
고민을 좀 하고 문제를 다시 읽어보니 조건을 보았고 아래와 같이 코드를 다시 작성하였다.
isMate
private static boolean isMate(String s) {
int capacity = s.length(); // 스택의 용량
int ptr = 0; // 스택 포인터
char[] stk = new char[capacity]; // 스택
// push & pop
for(int i = 0; i < capacity; i++) { // 스택의 길이는 용량만큼의 길이를 가지고 있음 (그만큼 반복함)
char ch = s.charAt(i);
if (ch == '(') { // 잘라낸 문자열을 하나하나 비교하고 열리는 괄호인 경우 스택에 푸시한다.
stk[ptr++] = ch;
} else {
if (ptr <= 0) { // 닫힌 괄호가 나왔는데 스택이 비어있으면 올바르지 않은 괄호다.
return false; // 바로 false를 반환해주자. (짝이 안맞는것이다.)
}
ptr--; // 스택 포인터를 -1 해준다.
}
}
return ptr == 0; // 문제가 없다면 true가 반환될것이다.
}포인트
1. '(' 열린 괄호인 경우에는 전부 스택에 푸시하자 (열린 괄호로 시작해야 올바른 괄호니까)
2. 아닌 경우(닫힌 괄호인 경우)인데 스택이 비어있는 경우에는 애초에 처음부터 닫힌 괄호니 시작부터 틀렸다. (곧바로 false를 반환해주자)
3. 스택포인터를 잘 보자. 푸시할때 증가시키고 닫힌괄호인 경우 감소시켜준다.
(짝이 맞는 괄호들이라면 결국엔 스택포인터는 0이 될것이다.)
4. 어차피 스택포인터를 증감시켜도 스택내에 데이터는 사라지지 않는다.
실제로 팝을 하는건 아니지만 같은 효과를 낼 수 있다. 그리고 스택 내에 열린괄호를 푸시하지 않아도
ptr 변수를 증감시키기만 해도 같은 효과를 낼 수 있다.(이렇게 보니 스택아닌 스택을 구현한 느낌)
