[백준] 4949번 : 균형잡힌 세상 (JAVA)

점점 스택 관련 문제 막바지에 다다른다.

4번째 문제인 4949번 : 균형잡힌 세상 을 풀었다.

 

 

스택에 대해 아직 이해하지 못했다면 다음의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/17

[자료구조] 스택 (Stack)

 

바로 앞 문제인 9012번 : 괄호 에 대한 내용은 바로 앞의 블로그에서 확인하면 된다.

https://lucy1215.tistory.com/20

[백준] 9012번 : 괄호 (JAVA)

 

---

<문제>

 

<문제 해석>

스택을 이용하여 

주어진 문자열이 균형을 이루고 있는지 판단해라.

- 균형을 이루고 있으면 yes  /  그렇지 않다면 no 출력

 

 

 

<문제 해결>

이 문제는 이전 문제에서 괄호의 종류가 추가된 문제이다.

스택에 대해 이해하고 있고, 이전 문제를 풀었다면 어렵지 않게 풀었을 것이다.

 

이전 문제에서 괄호는 ' ( ' , ' ) ' 두 종류만 있었지만,

 

현재 문제에서 괄호는 ' ( ' , ' ) ' , ' [ ' , ' ] ' 로 총 4가지가 있다.

이 문제 또한, stack을 이용하여 문제를 풀 수 있다.

 

 

<알고리즘>

1. 문자열이 ' ( ' || ' [ ' 일 때, stack에 해당 문자열을 push 한다.

 

 

2. 문자열이 ' ) ' 일 때, stack의 맨 위 문자열을 확인하고,

 

                 1. stack의 맨위 문자열이 ' ( ' 이면 stack에 pop()을 실행한다.

                     - ' ) ' 문자와 괄호 짝을 이뤘기 때문이다.

 

                 2. 해당 stack이 비었을 경우 || stack의 맨 위 문자열이 ' ] ' 일 경우, 올바른 괄호가 아니다.

                     - ' ) ' 문자열이 짝을 이룰 수 있는 괄호가 없기 때문이다.

                     - 'no' 출력

 

 

3. 문자열이 ' ] ' 일 때, stack의 맨 위 문자열을 확인하고,

 

                 1. stack의 맨위 문자열이 ' [ ' 이면 stack에 pop()을 실행한다.

                     - ' ] ' 문자와 괄호 짝을 이뤘기 때문이다.

 

                 2. 해당 stack이 비었을 경우 || stack의 맨 위 문자열이 ' ) ' 일 경우, 올바른 괄호가 아니다.

                     - ' ] ' 문자열이 짝을 이룰 수 있는 괄호가 없기 때문이다.

                     - 'no' 출력

 

 

4. 최종적으로 stack이 비었다면 yes,  그렇지 않다면  no를 출력한다.

 

 

 

 

<코드>

import java.util.Scanner;
import java.util.Stack;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
 
		String s;
		
		while(true) {		
			s = in.nextLine();
			
			if(s.equals(".")) {
				break;
			}		
			System.out.println(run(s));
		}
	}
	
    
	public static String run(String s) {
		
		Stack<Character> stack = new Stack<>();
		
		for(int i = 0; i < s.length(); i++) {
			
			char c = s.charAt(i);
			
			if(c == '(' || c == '[') {
				stack.push(c);
			}
			
			else if(c == ')') {
				
				if(stack.empty() || stack.peek() != '(') {
					return "no";
				}
				else {
					stack.pop();
				}
			}
			
			else if(c == ']') {
				
				if(stack.empty() || stack.peek() != '[') {
					return "no";
				}
				else {
					stack.pop();
				}
			}
		}
		
		if(stack.empty()) {
			return "yes";
		}
		else {
			return "no";
		}
	}
 
}

 

 

다음에는 스택 마지막 문제인 1874번 : 스택 수열 을 풀어보겠다.

---

https://www.acmicpc.net/problem/4949

4949번: 균형잡힌 세상