[SWEA][JAVA]1218 - 괄호 짝짓기

문제 출처 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14eWb6AAkCFAYD&categoryId=AV14eWb6AAkCFAYD&categoryType=CODE&problemTitle=1218&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

문제

 

 

설명

문제를 잘못 이해해서 그렇게 난이도가 높은 문제는 아니었는데도 불구하고 헤멨던 문제입니다ㅜㅜ

이 문제에서는 교차관계 말고 포함 관계만 유효한 것으로 보는데, 저는 교차 관계로 생각해서 어쨌든 종류의 짝이 다 맞아야 한다고 잘못 생각했었습니다.

즉, [ ( ) ] 나, []() 등의 경우는 유효하지만, [ ( ] ) 이런 경우는 유효하지 않은 것입니다. 결국, 여는 괄호가 하나 나오면 바로 다음에 같은 종류의 닫는 괄호가 나와야 하므로, 이 점을 주의해 스택을 사용해서 풀면 쉽게 풀리는 문제입니다.

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class SWEA1218_Bracket {

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Character> stack = new Stack<>();
		
		for(int tc=1; tc<=10; tc++) {
			int num = Integer.parseInt(br.readLine());
			String s = br.readLine();
			int answer=1; //일단 valid로 초기화
			
			stack.clear(); //새로운 테케 들어가기 전 clear
			
			for(int i=0; i<num; i++) { //받은 문자열의 처음부터 끝가지 한 번 순회
				
				if(s.charAt(i)=='{' || s.charAt(i)=='[' || s.charAt(i)=='(' || s.charAt(i)=='<') { //여는 괄호라면
					stack.push(s.charAt(i));
				}else { //닫는 괄호라면
					if(!stack.isEmpty()) {
						if(stack.peek()=='{' && s.charAt(i)=='}')
							stack.pop();
						else if(stack.peek()=='[' && s.charAt(i)==']')
							stack.pop();
						else if(stack.peek()=='(' && s.charAt(i)==')')
							stack.pop();
						else if(stack.peek()=='<' && s.charAt(i)=='>')
							stack.pop();
						else { //괄호가 포함 관계만 성립하므로, invalid
							answer=0; break;
						  }
						}
					else { answer=0; break;} //스택이 비어있으면 invalid
					  }
				}
			
			answer = stack.size()==0 ? 1 : 0; //끝가지 다 순회하고 나와서, 스택이 다 비어있어야 valid
			
			System.out.println("#"+tc+" "+answer);
			
		}
	}
}