문제
문자열이 여러 줄 주어지며 각 줄에 대해 괄호가 균형을 이루는지 판단하는 문제이다. 소괄호 (, ), 대괄호 [, ] 두 종류의 괄호가 존재하며, 같은 종류의 괄호끼리만 매칭된다. 마침표(.) 하나만 있는 줄이 입력되면 종료한다.
입력
한 줄씩 문자열이 주어진다. 문자열은 알파벳, 공백, 괄호, 마침표를 포함할 수 있다. 마지막 입력은 .이다.
출력
각 줄에 대해 괄호가 균형을 이루면 yes, 그렇지 않으면 no를 출력한다.
예제
| 입력 | 출력 |
|---|---|
So when I die (the [first] I will see in (heaven) is a score with no errors) . | yes |
풀이
스택을 이용한 괄호 유효성 검사로 해결한다. 여는 괄호는 스택에 push하고, 닫는 괄호를 만나면 스택에서 pop하여 쌍을 맞춘다.
- 종료 조건인
.한 글자를 만날 때까지 줄을 반복 읽는다. - 각 줄의 문자를 순회하며
[,(이외의 문자는 건너뛴다. [,(는 스택에 push한다.],)를 만나면 스택이 비어있거나, pop한 여는 괄호와 종류가 다르면no로 판정하고 루프를 중단한다.- 루프 종료 후 스택이 비어있어야만
yes이다.
핵심 아이디어: 여는 괄호와 닫는 괄호의 인덱스를 비교하여 쌍을 확인한다. 스택이 비어있는 상태에서 닫는 괄호가 나오거나 순회 후 스택에 여는 괄호가 남아있으면 불균형이다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Day16BOJ4949균형잡힌괄호 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
char[] str;
while (true) {
Stack<Character> stack = new Stack<>();
String ans = "yes";
String tmp = br.readLine();
if (tmp.equals("."))
break;
str = tmp.toCharArray();
for (char c : str) {
if (!"[{(]})".contains(c + ""))
continue;
if ("[{(".contains(c + "")) {
stack.push(c);
continue;
}
if (stack.isEmpty() || "[{(".indexOf(stack.pop()) != "]})".indexOf(c)) {
ans = "no";
break;
}
}
ans = stack.isEmpty() ? ans : "no";
sb.append(ans).append("\n");
}
System.out.println(sb);
br.close();
}
}복잡도
- 시간: O(N × L) — N은 입력 줄 수, L은 각 줄의 길이
- 공간: O(L) — 각 줄에서 스택에 최대 L/2개의 여는 괄호 저장