1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14eWb6AAkCFAYD 

SW Expert Academy

 

문제 해석

4 종류의 괄호문자들 '()', '[]', '{}', '<>' 로 이루어진 문자열이 주어진다.
이 문자열에 사용된 괄호들의 짝이 모두 맞는지 판별하는 프로그램을 작성한다.

 

예를 들어 아래와 같은 문자열은 유효하다고 판단할 수 있다.

아래와 같은 문자열은 유효하지 않은 문자열이다. 붉은색으로 표시된 괄호의 짝을 찾을 수 없기 때문이다.

아래 문자열은 열고 닫는 괄호의 개수는 유효하나 짝이 맞지 않는 괄호가 사용 되었기 때문에 유효하지 않다.

 

문제 풀이 전 설계

선입선출의 스택 자료구조를 이용하여 풀이합니다.

Java에는 stack 자료구조가 존재하지만 이는 Legacy이기 때문에 Deque 자료구조를 사용할 예정입니다.

 

{, [ (, < 를 만나면 stack에 push를 하고 그렇지 않으면 pop을하며 대칭이되는지 비교합니다.

 

대칭이 이루어지지 않으면 바로 유효하지 않으니 종료하며 문자열이 모두 push, pop 되었는데 스택이 비어있지 않으면 이또한 문자열이 유효하지 않은것으로 판단합니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Solution_1218_괄호짝짓기 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		for (int tc = 1; tc <= 10; tc++) {
			int result = 1;
			int length = Integer.parseInt(br.readLine());
			Deque<Character> stack = new ArrayDeque<>();
			String problemStr = br.readLine();
			inner: for (int i = 0; i < length; i++) {
				char tempChar = problemStr.charAt(i);
				if (isOpen(tempChar)) {
					stack.addLast(tempChar);
				} else {
					// isClose : '>' , ')', ']', ,'}'
					// stack.pollLast()
					char tempPop = stack.pollLast();
					switch (tempChar) {
					case ')':
						if (tempPop != '(') {
							result = 0;
							break inner;
						}
						break;
					case ']':
						if (tempPop != '[') {
							result = 0;
							break inner;
						}
						break;
					case '}':
						if (tempPop != '{') {
							result = 0;
							break inner;
						}
						break;
					case '>':
						if (tempPop != '<') {
							result = 0;
							break inner;
						}
						break;
					}

				} // else끝
			} // inner for끝
			if (stack.size() > 0) {
				result = 0;
			}
			sb.append("#" + tc + " " + result + "\n");
		}
		System.out.println(sb);
	}

	static boolean isOpen(char temp) {
		return temp == '(' || temp == '<' || temp == '{' || temp == '[';
	}

}