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

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

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14eWb6AAkCFAYD&categoryId=AV14eWb6AAkCFAYD&categoryType=CODE&problemTitle=%EA%B4%84%ED%98%B8+%EC%A7%9D%EC%A7%93%EA%B8%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy

 

// 210204

import java.io.*;
import java.util.*;

public class Solution_D4_1218_괄호짝짓기 {
	static int N;
	static char[] stack;

	private static boolean isParenthis(char[] arr) {
		int top = -1;
		
		for (int i=0; i<N; i++) {
			char c = arr[i];
			switch (c) {
				// 여는 괄호라면 stack에 저장
				case '(' : stack[++top] = '('; break;
				case '[' : stack[++top] = '['; break;
				case '{' : stack[++top] = '{'; break;
				case '<' : stack[++top] = '<'; break;
				
				// 닫는 괄호라면 stack[top]와 짝인지 비교한다.
				case ')' : {
					if (top < 0 ) return false;
					if (stack[top] ==  '(' ) {
						top--;
					}
					else return false;
					break;
				}
				
				case ']' : {	
					if (top < 0 ) return false;
					if (stack[top] == '[') {
						top--;
					}
					else return false;
					break;
				}
				
				case '}' : {
					if (top < 0 ) return false;
					if (stack[top] == '{') {
						top--;
					}
					else return false;
					break;
				}
				
				case '>' : {
					if (top < 0 ) return false;
					if (stack[top] == '<') {
						top--;
					}
					else return false;
					break;
				} 
			} // switch
		} // for
		if (top != -1) return false;
		else return true;
	}
	
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		for(int tc=1; tc<=10; tc++) {
			N = sc.nextInt();
			char[] arr = sc.next().toCharArray();
			stack = new char[N];
			
			int ans = (isParenthis(arr)==true) ? 1 : 0;
			System.out.println("#" + tc + " " + ans);
		}

		sc.close();
	}

}

 

배열을 스택으로 사용해 풀었다.
 
1. 비어있는 스택의 top 위치는 -1이다.
2. 여는 괄호를 만나면 ++top, 스택에 집어넣는다.
3. 닫는 괄호를 만났을 때
 1) top=-1이라면 스택이 비어있는 것이니 false 리턴.
 2) 스택의 맨 위 (stack[top]) 자신과 짝인 여는 괄호라면, 스택에서 여는 괄호를 빼준다. 
 3) 1, 2) 사례에 해당하지 않는다면 stack[top]이 여는 괄호가 아니거나 자신과 짝이 아닌 여는 괄호인 것이니 false를 리턴.