[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;
public class p1218 {
static Stack<Character> stack;
static Map<Character, Character> map = new HashMap<>();
public static int findPair(String str) {
stack = new Stack<>();
for(int i=0; i<str.length(); i++) {
if(map.containsKey(str.charAt(i))) {
stack.push(str.charAt(i));
}
else {
if (map.get(stack.pop()) != str.charAt(i)) {
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()));
}
}
}