Problem
괄호가 균형을 제대로 이루는지 확인하는 문제입니다.
Solution
간단한 짝 맞추는 문제입니다.
문제 조건이 복잡해 보이지만 결론은 여는 괄호와 닫는 괄호의 쌍이 일치하는 지 확인하라는 문제입니다.
Stack
자료구조를 이용해서 풀 수도 있고, 간단히 char[]
배열과 cursor
를 이용하여 해결 할 수도 있습니다.
여는 괄호가 들어오면 스택에 넣어두고, 닫는 괄호를 만나면 스택에서 하나 꺼냅니다.
스택에서 꺼낸 여는 괄호와 짝이 맞다면 계속해서 진행하고, 스택이 비어있거나 짝이 맞지 않으면 중지합니다.
속도는 배열을 쓴게 더 빠릅니다.
Java Code 1
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (true) {
String input = br.readLine();
if (input.equals(".")) {
bw.flush();
return;
}
bw.write(isBalanced(input));
}
}
// use Stack
static String isBalanced(String s) {
Stack<Character> stack = new Stack<>();
boolean result = true;
for (char one : s.toCharArray()) {
if (one == '(' || one == '[') {
stack.push(one);
} else if (one == ')') {
if (stack.isEmpty() || stack.pop() != '(') {
result = false;
break;
}
} else if (one == ']') {
if (stack.isEmpty() || stack.pop() != '[') {
result = false;
break;
}
}
}
if (!stack.isEmpty()) {
result = false;
}
return result ? "yes\n" : "no\n";
}
}
Java Code 2
import java.util.*;
import java.io.*;
class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
while (true) {
String input = br.readLine();
if (input.equals(".")) {
bw.flush();
return;
}
bw.write(isBalanced(input));
}
}
// use char[] array and cursor
static String isBalanced(String s) {
char[] stack = new char[s.length()];
int cursor = 0;
boolean result = true;
for (char one : s.toCharArray()) {
switch (one) {
case '(':
case '[':
stack[cursor++] = one;
break;
case ')':
if (cursor == 0 || stack[--cursor] != '(') {
return "no\n";
}
break;
case ']':
if (cursor == 0 || stack[--cursor] != '[') {
return "no\n";
}
break;
}
}
if (cursor > 0) {
result = false;
}
return result ? "yes\n" : "no\n";
}
}
'알고리즘 문제 > 백준' 카테고리의 다른 글
백준 14954번. Happy Number (Java) (0) | 2020.04.03 |
---|---|
백준 13913번. 숨바꼭질 4 (Java) (1) | 2020.03.30 |
백준 12851번. 숨바꼭질 2 (Java) (3) | 2020.03.29 |
백준 2293 동전 1 (Java) (0) | 2020.03.28 |
백준 2437번. 저울 (Java) (2) | 2020.03.17 |