[JAVA] SWEA 1218번 괄호 짝짓기

문제

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

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

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

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

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

입력

각 테스트 케이스의 첫 번째 줄에는 테스트케이스의 길이가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다.

총 10개의 테스트케이스가 주어진다.

출력

#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 유효성 여부를 1 또는 0으로 표시한다 (1 - 유효함, 0 - 유효하지 않음).

풀이

pair인 괄호를 찾아 반환하는 문제이다.

 

입력을 받고, ({[<의 경우 스택에 저장하고, )}]> 괄호일 경우 스택의 값을 하나 꺼내어 비교를 통해 pair인지 확인한다.

 

import java.util.Scanner;

public class 괄호짝짓기 {
	public static int tc;
	public static char[] stack = new char[10000];
	public static int top;
	public static boolean answer;
	
	public static boolean checkPair(char[] pairs) {
		top = -1;
		for (int i = 0; i < pairs.length; i++) {
			switch(pairs[i]) {
			case '(': case '{': case '[': case '<':
				stack[++top] = pairs[i]; break;
			case ')':
				if (stack[top] == '(') top--; else return false; break;
			case '}':
				if (stack[top] == '{') top--; else return false; break;
			case ']':
				if (stack[top] == '[') top--; else return false; break;
			case '>':
				if (stack[top] == '<') top--; else return false; break;
			}
		}
		if (top != -1) return false;
		return true;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		for (int test_case = 1; test_case <= 10; test_case++) {
			tc = sc.nextInt();
			char [] pairs = sc.next().toCharArray();
		
			System.out.println("#" + test_case + " " + (checkPair(pairs) ? 1 : 0));
		}
	}
}