[Java] SWEA1218_괄호짝짓기

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

SW Expert Academy

[문제]

4 종류의 괄호문자들 '()', '[]', '{}', '<>' 로 이루어진 문자열이 주어진다.

이 문자열에 사용된 괄호들의 짝이 모두 맞는지 판별하는 프로그램을 작성한다.

 

유효하면 1, 유효하지 않으면 0 출력

 

[입력]

182
(({<(({{[[[[<<[[(<[[{([{{{[<[[[{<<(<[[{}[]{}{}[]]]><><>{})[]{}><>[]<>><>}][]]<>{}]>]()}()()(){}}}{}][])(){}<>()}]{}[]]>()[][][]){}]]{}[]<>><>{}[]{}<>>]]]][]{}{}[]()}}))>}<>{}()))[][]

 

[출력]

#1 1

 

[풀이]

규칙 

1. '()', '[]', '{}', '<>' 각자 쌍이 맞을 것

2. 열린괄호로 시작해서 닫힌 괄호로 끝날 것

 

위 두가지 규칙을 파악 후, 스택을 이용하여 풀었다.

열린 괄호라면 스택에 넣어두고, 닫힌 괄호라면 스택의 top (가장 최근의 열린괄호가)과 비교한다. 

top이 자신의 짝이라면 top을 삭제한다.

유효한 괄호식이라면 마지막엔 스택이 비어있을 것이다. 

스택이 비어있다면 1을 출력, 스택이 비어있지 않다면 0을 출력한다.

 

import java.util.Scanner;
import java.util.Stack;

public class SWEA1218 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int tc = 10;
		for (int t = 1; t <= tc; t++) {
			Stack<Character> stack = new Stack<Character>();
			
			int num = sc.nextInt();
			sc.nextLine();
			String s = sc.nextLine();
			
			for(int i = 0; i < s.length(); i++) {	//s.length() 대신 num도 가능
				char c = s.charAt(i);
				
				if(c == ')' && stack.peek() == '(') stack.pop();	//닫힌괄호들은 check
				else if(c == ']' && stack.peek() == '[') stack.pop();
				else if(c == '}' && stack.peek() == '{') stack.pop();
				else if(c == '>' && stack.peek() == '<') stack.pop();
				else {
					stack.push(c);		//열린 괄호들은 push
				}
			}
		if(stack.isEmpty())		//스택 비어있으면 1출력
			System.out.printf("#%d %d\n",t,1);
		else 
			System.out.printf("#%d %d\n",t,0);
		
		}

	}

}