[백준알고리즘-JAVA]4949번 풀이(균형잡힌 세상) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 4949번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 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

성공 코드

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

public class Main {

	static int T;
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		//T = Integer.parseInt(br.readLine());

		while(true) {
			
			
			String end = br.readLine();
			if(end.equals("."))
				break;
			
			StringTokenizer st = new StringTokenizer(end,"[]()",true);

			Stack<String> stk = new Stack<>();
			
			boolean flag = true;
			
			while(st.hasMoreTokens()) {
				String temp = st.nextToken();
				
				if(temp.equals("(") || temp.equals("[")) {
					stk.push(temp);
				}else if(temp.equals(")")) {
					if(stk.isEmpty()) {
						flag = false;
						break;
					}
					if(stk.peek().equals("("))
						stk.pop();
					else {
						flag = false;
						break;
					}
				}else if(temp.equals("]")) {
					if(stk.isEmpty()) {
						flag = false;
						break;
					}
					if(stk.peek().equals("["))
						stk.pop();
					else {
						flag = false;
						break;
					}
				}

			}

			
			if(flag && stk.isEmpty())
				sb.append("yes").append("\n");
			else
				sb.append("no").append("\n");
		}
		
	
		System.out.println(sb);

		}
	
	
}

하... 해당 알고리즘은 진작에 풀었지만 마지막 출력을 대문자로 YES, NO로 해놔서 2시간을 헤맸던 문제였습니다... ㅜㅜ 어디가 틀렸는지 몰라서 이것저것 고치다가 결국 이런 코드가 나와버렸네요...

 

해당 문제의 핵심은 간단합니다. () [] 이 두 괄호가 균형에 맞게 잘 있냐 이문제입니다.

 

간단합니다. ) ] 둘 중에 하나가 들어오면 스택의 가장 윗부분이 ( [ 인지를 비교해주면 끝이거든요 STEP을 따라서 좀 더 쉽게 이해해 보도록 하죠.

---

알고리즘 흐름도

 입력받기 -> [, ( 스택에 넣기 -> ) ] 들어올 시 스택 TOP확인 -> 아닐 시 NO출력 / 맞으면 YES출력

---

STEP1 입력받기

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true) {
			
			String end = br.readLine();
			if(end.equals("."))
				break;
			
			StringTokenizer st = new StringTokenizer(end,"[]()",true);

			Stack<String> stk = new Stack<>();
			
			boolean flag = true;

		}

저 같은 경우는 입력을 이런 식으로 초래했습니다. 입력을 받고 우선 끝나는. 인지 확인을 합니다..이라면 해당 WHILE문을 빠져나오도록 하였죠. 받은 입력을 각 괄호로 나눠줍니다. (뒤에 TRUE는 구분자도 표현하라는 의미)

 

이런 식으로라면 쉽겠죠? 판별할 STACK을 하나 선언하고 flag로 사용할 boolean변수도 선언해 줍니다.

(아직까지는 flag가 왜 필요한지 모를 수도 있습니다. 과감히 생략하고 하셔도 됩니다.)

---

STEP2 비교하여 넣기

			while(st.hasMoreTokens()) {
				String temp = st.nextToken();
				
				if(temp.equals("(") || temp.equals("[")) {
					stk.push(temp);
				}else if(temp.equals(")")) {

				}else if(temp.equals("]")) {

				}

			}

이런 식으로 작성해 줍니다. 나누어진 st 토큰들을 하나씩 꺼내면서 열린 괄호 2개가 들어오면 무조건 스택에 넣어줍니다. 그리고 만약 닫힌 괄호가 들어오면 확인해 줘야 합니다.

			while(st.hasMoreTokens()) {
				String temp = st.nextToken();
				
				if(temp.equals("(") || temp.equals("[")) {
					stk.push(temp);
				}else if(temp.equals(")")) {
					if(stk.isEmpty()) {
						flag = false;
						break;
					}
					if(stk.peek().equals("("))
						stk.pop();
					else {
						flag = false;
						break;
					}
				}else if(temp.equals("]")) {

				}

			}

만약 닫힌 괄호 ) 가들어온다면 확인해 줍니다. stk가 비어있다면, 오류겠죠? 이때 flag가 바로 쓰인답니다. flag가 false라면 no를 출력 아니라면 yes를 출력하면 되기 때문이죠.

 

그러고 해당 while문을 빠져나옵니다.

 

그렇지 않다면. 스택의 마지막 꼭대기에 있는 것을 확인하고 만약 그 괄호가 ( 라면 pop 해줍니다.

 

만약에 (가 아니라면 균형 잡힌 괄호가 되지 않기 때문에 flag에 false를 넣어주고 해당 while문을 빠져나옵니다.

 

 - 저도 처음에 문제가 이해가 되지 않았습니다. 뭐가 균형이지 그냥 () [] 개수만 맞추면 되나? 하고 생각했었는데 

Help( I [m being held prisoner in a fortune cookie factory)].

 

해당 예제를 보고 이해했습니다.

 

( [ 이런 식의 순서로 들어왔으면 ] ) 이런 식의 순서로 닫혀야 한다는 것을.

 

그렇다면 아주 간단하지 않습니까? 우선 열린 괄호를 먼저 다 넣어주고 가장 마지막에 있는 게 ( [ 둘 중 무엇인지 파악한 후 닫힌 괄호가 나온다면, top과 비교만 해주면 끝이기 때문이죠

 

이처럼 ] 괄호도 처리해 주면 다음과 같습니다.

 

			while(st.hasMoreTokens()) {
				String temp = st.nextToken();
				
				if(temp.equals("(") || temp.equals("[")) {
					stk.push(temp);
				}else if(temp.equals(")")) {
					if(stk.isEmpty()) {
						flag = false;
						break;
					}
					if(stk.peek().equals("("))
						stk.pop();
					else {
						flag = false;
						break;
					}
				}else if(temp.equals("]")) {
					if(stk.isEmpty()) {
						flag = false;
						break;
					}
					if(stk.peek().equals("["))
						stk.pop();
					else {
						flag = false;
						break;
					}
				}

			}

---

 

STEP 3 출력하기

if(flag && stk.isEmpty())
				sb.append("yes").append("\n");
			else
				sb.append("no").append("\n");

하... 이거 때문에 2시간을 낭비했습니다..... 소문자 확인해 주세요..

 

여기서 왜 flag와 stk.isEmpty 두 개를 모두 해주었냐면 열린 괄호만 있으면 flag가 true로 나오기 때문입니다.