[백준/java] 4949번 : 균형잡힌 세상

딱 기본적인 stack을 활용한 문제이다.

 

• 문제 : https://www.acmicpc.net/problem/4949

---

<풀이>

• 괄호를 만나면 stack에 넣는다.
• 오른쪽 괄호의 경우 stack의 top에 있는 괄호와 짝을 이룰 경우 stack에 넣지 않고 stack에 들어있는 왼쪽 괄호를 pop한다.

• 최종적으로 stack이 비어있으면 yes를 출력한다.

 

아래는 java에서 제공하는 Stack을 사용한 풀이이다.

import java.util.Stack;
import java.util.Scanner;

public class BOJ4949 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            String str = sc.nextLine();
            Stack<Character> stack = new Stack<>();

            if (str.equals("."))
                break;

            for (int i = 0; i < str.length(); i++) {
								// 괄호를 만났을때 
                if (str.charAt(i) == '[' || str.charAt(i) == ']' || str.charAt(i) == '(' || str.charAt(i) == ')') {
										// 넣으려는 괄호가 오른쪽 괄호일 경우는 stack에 왼쪽괄호가 top에 존재할때 stack에서 왼쪽 괄호를 빼낸다
                    if ((!stack.empty() && stack.peek() == '[' && str.charAt(i) == ']') || (!stack.empty() && stack.peek() == '(' && str.charAt(i) == ')')) {
                        stack.pop();
                    } else {
												// 괄호는 스택에 저장한다
                        stack.push(str.charAt(i));
                    }
                }
            }
            System.out.println(stack.isEmpty() ? "yes" : "no");
        }
    }
}

 

아래는 ArrayList를 이용해서 직접 Stack을 구현해서 푼 풀이이다.

import java.util.*;

/*
백준 4949번 균형잡힌 세상
분류 : stack
직접 스택 구현해서 풀기
* */


public class BOJ4949_2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (true) {
            String str = scanner.nextLine();
            Stack stack = new Stack();
            if (str.equals("."))
                break;

            for (int i = 0; i < str.length(); i++) {
                if (str.charAt(i) == '[' || str.charAt(i) == ']' || str.charAt(i) == '(' || str.charAt(i) == ')') {
                    if ((!stack.isEmpty() && stack.peek() == '[' && str.charAt(i) == ']') || (!stack.isEmpty() && stack.peek() == '(' && str.charAt(i) == ')')) {
                        stack.pop();
                    } else {
                        stack.push(str.charAt(i));
                    }
                }
            }
            System.out.println(stack.isEmpty() ? "yes" : "no");
        }
    }

    private static class Stack {
        private List<Character> elements;
        private int elementSize;

        public Stack() {
            this.elements = new ArrayList<>();
            this.elementSize = 0;
        }

        public void push(char element) {
            elements.add(element);
            elementSize++;
        }

        public void pop() {
            if (isEmpty()) {
                throw new EmptyStackException();
            }

            elements.remove(elementSize - 1);
            elementSize--;
        }

        public char peek() {
            if (isEmpty()) {
                throw new EmptyStackException();
            }

            return elements.get(elementSize - 1);
        }

        public boolean isEmpty() {
            if (elementSize == 0) {
                return true;
            }
            return false;
        }


    }
}