[S/W 문제해결 기본] 4일차 - 괄호 짝짓기 (D4)

문제 링크

• stack 활용 문제!
• 괄호의 짝이 맞는지 확인하는 문제
• 4 종류의 괄호문자들 '()', '[]', '{}', '<>' 로 이루어진 문자열
• 괄호 짝을 Map으로 선언한다

Map<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
map.put('<', '>');

• 문자열을 앞에서 읽고 key(열린괄호)이면 스택에 push
• 키가 아닐 때(닫힌괄호일 때)
  • 스택의 top(열린괄호)을 키로 하는 value(닫힌괄호)와 현재 토큰이 같은지 비교
  • 같으면 pop / 다르면 괄호가 맞지 않으므로 false 반환
    cf> 스택이 비어있으면 괄호의 짝이 맞지 않으니 false 반환

Solution

package swea;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;

// [S/W 문제해결 기본] 4일차 - 괄호 짝짓기
public class p1218 {
	static Stack<Character> stack;
	static Map<Character, Character> map = new HashMap<>();
	
	public static int findPair(String str) {
		stack = new Stack<>(); // stack 새로 생성
		for(int i=0; i<str.length(); i++) { 
			if(map.containsKey(str.charAt(i))) { // 열린 괄호라면
				stack.push(str.charAt(i)); // 스택에 push
			}
			else { // 닫힌 괄호 일 때
				if (map.get(stack.pop()) != str.charAt(i)) { // 스택의 top과 짝 괄호가 아니라면
					return 0;
				}
			}
		}
		
		if (!stack.isEmpty()) { // 열린괄호의 수가 닫힌괄호의 수보다 많을 때
			return 0;
		}
		return 1;
	}
	
	public static void main(String[] args) {
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');
		map.put('<', '>');
		
		Scanner sc = new Scanner(System.in);
		for(int t=1; t<=10; t++) {
			int N = sc.nextInt();
			
			System.out.printf("#%d %d\n", t, findPair(sc.next()));

		}
	}
}