https://www.acmicpc.net/problem/4949
문제
> 세계는 균형이 잘 잡혀있어야 한다.
> 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다.
> 정민이의 임무는 어떤 문자열이 주어졌을 때,
괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
> 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고,
문자열이 균형을 이루는 조건은 아래와 같다.
1. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
2. 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
3. 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
4. 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
5. 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.
> 정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.접근
입력받은 문자열을 순회하며 (, [, ), ]가 나올 때에 대해 처리를 구현해준다.
(와 [는 스택에 해당 문자들을 넣어준다.
)와 ]는 스택의 peek에 해당하는 값을 가져와서 같으면 스택을 pop하고 다르면 균형이 맞지 않게 되므로 (ex ( ]이렇게 문자열에 있는 상황) no를 출력한다.
이제 이 과정을 다 처리하고 스택이 비어있다면 yes, 아니면 no를 출력한다.
문제해결
> while문으로 문자열을 계속 받아와 str에 저장한다.
> .문자가 들어오면 멈춰야 하므로 str이 .인지 확인하고 맞다면 깨준다.
> 문자열을 끝까지 보지 않고도 균형이 깨졌다는걸 나타내기 위해 boolean변수 valid를 선언한다.
> 괄호문자를 담을 문자형 스택 s를 선언한다.
> 입력받은 문자열을 순회하며 ( 와 \[ 가 들어오면 스택에 집어 넣는다.
> 이제 )와 ]가 나오면 스택과 짝을 맞춰야 하므로 각각에 대해 처리한다.
> 해당 괄호가 나왔는데 스택이 비어있다면 균형이 맞지않는것이고,
최상단 peek랑 종류가 다른 괄호면 균형이 맞지 않는다.
> 따라서 이 경우 문자열을 더 순회하지 않고 미리 no를 출력하고 valid를 false로 바꾼다.
> 두 경우가 아닌, 스택이 비어있지 않으며 peek와 같은 종류의 괄호라면 pop으로 스택의 짝을 맞춰준다.
> 위 과정을 )와 ]에 대해 각각 해준다.
> 이제 문자열을 다 순회하고 나면 valid가 true인 (나 \[가 닫는 괄호들 보다 더 많이 들어왔거나, 딱 맞게 들어온 상황에 대해 따진다.
> 스택이 비어있으면 짝이 다 맞는거라 yes고 비어있지 않으면 짝 안맞는 애가 남았다는 뜻이므로 no출력한다.
코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main
{
//4949번 균형잡힌 세상
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
while(true) {
String str = br.readLine();
if(str.equals(".")) break;
boolean valid = true;
Stack<Character> s = new Stack<>();
for(int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
if(c == '(' || c == '[') s.push(c);
else if(c == ')') {
if(s.empty() || s.peek() != '(') { //큐가 비거나, top()이 같지 않으면
sb.append("no").append('\n');
valid = false;
break;
}
s.pop(); //큐가 안비었는데 top이 같다면
}
else if (c == ']') {
if (s.empty() || s.peek() != '[') {
sb.append("no").append('\n');
valid = false;
break;
}
s.pop();
}
}
if(valid) sb.append(s.empty() ? "yes" : "no").append('\n');
}
System.out.print(sb);
}
}
후기
문제 이해가 빡셌다. 약간 불편하게 까다로운 문제로 여렵진 않았다.
