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

문제

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

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

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

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

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

 

풀이방법

스택을 이용해 해결한다.

 

1) '{' , '[' , '<', '(' 기호가 나오면 스택에 담는다.

 

2) '}', ']', '>', ')' 닫는 기호가 나올 경우 스택에 담겨진 top의 기호와 쌍을 이루는지 확인한다.

 

3) 2의 조건을 만족하면 pop으로 스택의 top을 삭제한다.

 

4) 모든 입력을 다 받아들인 후 스택이 비었다면 유효하고 하나라도 있다면 유효하지 않는다.

 

소스코드

package samsung;

import java.util.*;

public class s_1218 {
	public static void main(String[] ags) {
		Scanner sc = new Scanner(System.in);
		for(int t = 1; t <= 10; t++) {
			int tc = sc.nextInt();
			String s = sc.next();
			Stack <Character> st = new Stack();
			int r = 0;
			for(int i = 0; i < s.length(); i++) {
				char c = s.charAt(i);
				
				if(c == ')' && st.peek() == '(') st.pop();
				else if(c == ']' && st.peek() == '[') st.pop();
				else if(c == '}' && st.peek() == '{') st.pop();
				else if(c == '>' && st.peek() == '<') st.pop();
				else {
					st.push(c);
				}
			}
			if(st.isEmpty()) r = 1;
			else r = 0;
			System.out.println("#" + t + " " + r);
		}
	}
}