[SWEA] 1218. 괄호 짝짓기 (Java)

문제

SW Expert Academy

 

풀이

0. 문제해석

스택을 이용하는 문제이다.

 

크게 스택이 비어있을 때와 비어있지 않을 때로 나눌 수 있는데,

 

1. 스택이 비어있을 때

닫는 괄호가 들어왔다면 괄호의 짝이 맞을 수 없으므로 불가능 리턴.

여는 괄호가 들어왔다면 스택에 추가

 

2. 스택이 비어있지 않을 때

닫는 괄호가 들어왔다면 짝이 맞는지 판별하여 짝이 안맞으면 불가능 리턴. 짝이 맞다면 그 짝을 pop

여는 괄호가 들어왔다면 스택에 추가

 

하는 방식으로 구현하면 된다.

 

1. 스택이 비어있을 때

 

2. 스택이 비어있지 않을 때

닫는 괄호라면 짝을 판별해준다.

 

3. 전체코드

// [SWEA] 1218. 괄호 짝짓기 (Java)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Solution {
	static Stack<Character> stack;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		for(int test = 1; test <= 10; test++) {
			int l = Integer.parseInt(br.readLine()); // 테스트케이스 길이
			stack = new Stack<>();
			int result = 1;
			
			String str = br.readLine();
			
			for(int i = 0; i < l; i++) {
				char ch = str.charAt(i);
				// 스택이 비어 있을 때
				if(stack.isEmpty()) {
					// 닫는 괄호가 들어왔다면
					if(CloseAdd(ch)) {
						result = 0;
						break;
					}
					// 닫는 괄호가 아니라면 스택에 추가
					else {
						stack.add(ch);
					}
				}
				
				// 스택이 비어있지 않을 때
				else {
					// 여는 괄호가 들어왔다면
					if(!CloseAdd(ch)) {
						stack.add(ch);
					}
					
					// 닫는 괄호가 들어왔을 때 짝이 맞는지 판별
					else if(CompareSign(stack.pop(),ch)) {
						result = 0;
						break;
					}
				}
			}
			System.out.println("#" + test + " " + result );
		}	
		br.close();
	}
	
	public static boolean CloseAdd(char ch) {
		if(ch == ')' || ch == ']' || ch == '}' || ch == '>') {
			return true;
		}
		return false;
	}
	
	public static boolean CompareSign(char pop, char add) {
		// 짝이 맞을 때 false 리턴
		if(pop == '(' && add == ')' || pop == '[' && add == ']'
			|| pop == '{' && add == '}' || pop == '<' && add == '>') {
			return false;
		}
		
		// 짝이 맞지 않을 때 true 리턴
		return true;
	}
	
}