ShaShaKa Dev Note

균형잡힌 세상

26 June 2019

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

이번은 주어진 문자열이 올바른 괄호열인지 판단하는 문제를 풀어보도록 하겠습니다.

import java.util.Scanner;

public class Main {

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);

		Stack stack = new Stack(100);

		while (true) {
			String val = sc.nextLine();
			if (val.equals(".")) {
				break;
			}
			stack.init();
			String ret = solve(stack, val);
			System.out.println(ret);
		}
	}

	private static String solve(Stack stack, String val) {

		for (int k = 0; k < val.length(); k++) {
			switch (val.charAt(k)) {
			case '(':
				stack.push(1);
				break;
			case '[':
				stack.push(2);
				break;
			case ')':
				if (stack.pop() != 1) {
					return "no";
				}
				break;
			case ']':
				if (stack.pop() != 2) {
					return "no";
				}
				break;
			default:
				break;
			}
		}

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

class Stack {
	private int top = -1;
	private int[] queue;

	Stack(int max) {
		queue = new int[max];
	}

	void init() {
		this.top = -1;
	}

	void push(int val) {
		top++;
		queue[top] = val;
	}

	int pop() {
		if (top == -1) {
			return -1;
		}
		int val = queue[top];
		top--;
		return val;
	}

	boolean isEmpty() {
		return top == -1;
	}
}

먼저 class를 통해 stack을 구현해주도록 합니다.
stack을 구현할 때, empty인 경우에 pop을 호출할 때는 -1을 리턴해주도록 합니다.
입력값을 받아 괄호가 시작하는 경우인 '(','['때는 각각 1,2를 stack에 넣어주고, 괄호를 닫는 경우인 ')',']'의 경우에는 pop을 해서 각각 1과 2가 나오는지 확인합니다.
각각의 값이 맞지않을 때는 "NO", 그리고 문자열의 조회가 모두 끝나고 stack에 값이 남아있는 경우도 "NO"를 리턴하도록 합니다.