[SWEA]1218번 괄호 짝짓기(JAVA)

0. 문제 링크

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

SW Expert Academy

 

1. 문제 설명

1) 4종류의 괄호문자들 (), [], {}, <> 로 이루어진 문자열의 유효성 판단

- 괄호의 개수는 유효한지

- 짝이 맞는 괄호가 사용되었는지

2) 10개의 테스트 케이스를 통해 유효성 여부(1 - 유효함 / 0 - 유효하지 않음) 출력하기

 

2. 입출력

// input
181
(({<(({{[[[[<<[[(<[[{([{{{[<[[[{<(<[[{}[]{}{}[]]]><><...
298
{(({[({([{(<[([(([<({[{{[[({{[({([<{(<[[((<{{[([{<<[{(<({[<(...
...

// output
#1 0
#2 0
...

 

3. 코드

import java.io.*;
import java.util.*;

public class swea1218 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		int T = 10; // 테스트 케이스의 개수
		for(int t = 1; t <= T; t++) {
			int ans = 1; // 유효함
			int N = Integer.parseInt(br.readLine()); // 테스트 케이스의 길이
			String str = br.readLine(); // 테스트 케이스의 문자열
			Stack<String> s = new Stack(); // 스택 생성
			
			for(int i = 0; i < N; i++) {
				if(ans == 0) break;
				String c = String.valueOf(str.charAt(i)); // 현재 넣을 괄호
				
				if(!s.isEmpty()) { // 스택이 비어 있지 않다면
					String tmp = s.peek(); // 제일 위에 있는거 가져옴
					switch(c) { // 닫는 괄호 짝이 맞으면 꺼내기
						case ")":
							if(tmp.equals("(")) s.pop();
							else ans = 0;
							break;
						case "}":
							if(tmp.equals("{")) s.pop();
							else ans = 0;
							break;
						case "]":
							if(tmp.equals("[")) s.pop();
							else ans = 0;
							break;
						case ">":
							if(tmp.equals("<")) s.pop();
							else ans = 0;
							break;
						case "(" :
							s.push(c);
							break;
						case "{" :
							s.push(c);
							break;
						case "[" :
							s.push(c);
							break;
						case "<" :
							s.push(c);
							break;
						default: // 아니면 유효하지 않음
							ans = 0;
							break;
					}
				} else { // 비어 있으면 추가
					s.push(c);
				}
			}

			System.out.printf("#%d %d\n", t, ans);
		}
	}
}

 

실행 결과

 

4. 회고

1) stack을 이용하여 닫는 괄호면 하나 꺼내서 짝이 맞는 열린 괄호인지 확인

2) 열린 괄호이면 stack에 넣기

 

5. Github

https://github.com/iihye/Algorithm/blob/main/SWEA/swea1218.java