[백준 4949] 균형잡힌 세상 / Java

링크 | https://www.acmicpc.net/problem/4949

문제 |

세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다.
문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다.

• 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다.
• 모든 왼쪽 대괄호("[")는 오른쪽 대괄호("]")와만 짝을 이뤄야 한다.
• 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다.
• 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다.
• 짝을 이루는 두 괄호가 있을 때, 그 사이에 있는 문자열도 균형이 잡혀야 한다.

정민이를 도와 문자열이 주어졌을 때 균형잡힌 문자열인지 아닌지를 판단해보자.

입력 |

하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 각 줄은 마침표(".")로 끝난다.
입력의 종료조건으로 맨 마지막에 점 하나(".")가 들어온다.

출력 |

각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.

예제 |

입력

So when I die (the [first] I will see in (heaven) is a score list).
[ first in ] ( first out ).
Half Moon tonight (At least it is better than no Moon at all].
A rope may form )( a trail in a maze.
Help( I[m being held prisoner in a fortune cookie factory)].
([ (([( [ ] ) ( ) (( ))] )) ]).
 .
.

출력

yes
yes
no
no
no
yes
yes

Solution |

• "."이 단독으로 들어올 때까지 문장 입력이 가능하도록 반복한다.

• String 객체끼리 더하는 방법은 메모리 할당과 해제를 발생시키기 때문에 StringBuilder을 이용하였다.
  stringBuilder.append("문자열 ").append("연결");

• 해당 문제가 dot과 eneter를 경계로 문자열을 인식하기 때문에 BufferedReader 사용하였다.

  • Scanner: 띄어쓰기와 엔터를 경계로 입력값을 인식.
  • BufferedReader: 엔터만을 경계로 인식하고 받은 데이터가 String으로 고정되기 때
    문에 데이터를 따로 가공해야하는 경우가 많지만 Scanner보다 상대적으로 속도가 빠름. 많은 데이터를 받아야하는 경우에 사용 권장.
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String s = br.readLine();

• 열린 괄호는 그대로 stack에 쌓아주고, 닫힌 중괄호와 닫힌 소괄호는 각각 stack의 그 전 값이 같은 종류의 열린 괄호라면 pop을 해주어 균형이 맞은 괄호를 제거해준다.

• 닫힌 괄호를 판단할 때 stack이 비어있으면 그전 stack을 가져오지 못해 에러가 발생하므로 비어있는지 같이 확인해준다.

• 짝이 맞지 않아 stack에 제거되지 않는 값들이 남아있는 경우 no를 리턴하고, stack이 비어있는 경우 yes를 리턴한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

public class BalancedWorld {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String s;
		
		while(true) {
			s = br.readLine();
			if (s.equals(".")) {
				break;
			}
			sb.append(balanced(s)).append('\n');
		}
		
		System.out.println(sb);
		br.close();
	}
	
	public static String balanced(String str) {
		Stack<String> stack = new Stack<String>();
		String[] splitStr = str.split("");
		stack.clear();
		
		for (int j=0; j<splitStr.length; j++){
			if (splitStr[j].equals("[") || splitStr[j].equals("(")) {
				stack.push(splitStr[j]);

			}else if(splitStr[j].equals("]")){
				if (!stack.empty() && stack.peek().equals("[")) {
					stack.pop();
				}else { return "no"; }
					
			}else if(splitStr[j].equals(")")){
				if (!stack.empty() && stack.peek().equals("(")) {
					stack.pop();
				}else { return "no"; }
			}
		}

		if (!stack.empty()) {
			return "no";
		}else {
			return "yes";
		}
	}
}