SWEA 1218 - 괄호짝짓기 (JAVA)

출처 - SW Expert Academy 

 

---

[ 알고리즘 ]  - Stack 

-> 닫힌 괄호가 나왔을 때, 가장 최근의 괄호와 짝이 맞다면 괄호 생성 가능 

열린 괄호 '( [ { <' : stack 에 쌓는다 

닫힌 괄호 ') ] } >:  stack 의 가장 위에 있는 ( 가장 최근 ) 괄호와 비교하여, 열린 괄호-닫힌괄호 짝이 생긴다면 pop 

        : 가장 위에 있는 괄호와 비교했을 때 짝이 맞지 않는다면, 이미 유효하지 않은 테스트 케이스 -> 일단 push 해둠  

           ( == > 결론적으로는, 스택이 비지 않고 쌓이기만 할 것이기 때문에 유효하지 않다고 판명 ) 

 

import java.io.*;
import java.util.*;
 
public class Solution {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb= new StringBuilder();
        
        for(int tc= 1; tc<=10; tc++) {
            Stack <Character> stack  = new Stack<>();
            
            int length = Integer.parseInt(br.readLine()); // 테스트케이스의 길이 
            int res= 0;
            String s= br.readLine();
            
            for(int i=0; i<length; i++) { // 테스트 케이스의 길이만큼 
                char c = s.charAt(i); // 하나씩 똑 떼내기 
                
                if(c==')' && stack.peek()== '(') stack.pop();
                else if(c==']' && stack.peek()== '[') 
                    stack.pop();
                else if(c=='}' && stack.peek()== '{') stack.pop();
                else if(c=='>' && stack.peek()== '<') stack.pop();
                // 열린괄호 들어왔을 떄 
                else  stack.push(c);
                
            }
            if(stack.isEmpty()) res=1;
            
            sb.append("#").append(tc).append(" ").append(res).append("\n");
        }// end of testcase for 10times
        System.out.println(sb);
    }
}

 - Stack : 괄호 하나하나를 문자로 취급하기 위해 Character 를 담을 수 있는 스택 생성 

 - charAt ( ) : 괄호 테스트 케이스를 하나의 문자열로 입력 받고 -> 앞에서 부터 쪼개어 테스트 케이스의 길이만큼,

for문 내부의 액션 취하기 

- res ( 유효 :1 / 유효 하지 않음 : 0 ) 을, 0 으로 초기화 ,

1) 테스트 케이스의 길이만큼 stack 작업 후, 스택이 비어있다면 , 괄호의 짝이 잘 맞았던 것 -> 1 

2) 스택이 비어있지 않다면, 짝이 맞지 않은 괄호들이 쌓여 있는 것 -> 0