[코딩 테스트 RUN] SWEA 수업 : 1218.괄호 짝짓기

 

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

 

[SW Expert Academy] 1218. 괄호짝짓기

SW Expert Academy

 

괄호짝짓기의 경우 스택의 대표적인 문제라고 할 수 있다. 계산기 문제에서도 간략하게 stack을 이야기했지만, 스택을 잘 모른다면 다음을 참고하면 좋다.

 

[Java] 자바 스택(Stack) 클래스 메서드 정리 및 활용

[Java] 자바 스택(Stack) 클래스 메서드 정리 및 활용

 

여기에서는 풀이만 이야기하도록 한다. 일단 여는 괄호를 스택에 push한다. 그리고 그 다음에 오는 문자(닫는 괄호일 확률이 높다)가 여는 괄호와 매칭하는지 확인한다. 이 경우 이미 push해둔 것을 pop으로 꺼내어 확인한다. 이렇게 반복을 하여 스택이 빌 때까지 반복하게 되는데, 만약에 모든 루프를 돌았음에도 비지 않았다면 유효하지 않으므로 0, 전부 비었다면 유효한 짝짓기이므로 1으로 출력한다.

 

 

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = 10;

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            Deque<Character> stack = new ArrayDeque<>();

            // 여는 괄호면 push하고, 아니라면 제일 위에있는 괄호와 비교한다.
            // 순서는 상관 없기 때문에 이렇게 비교해도 OK
            for(char c : br.readLine().toCharArray()){
                if(c == '(' || c == '[' || c == '{' || c == '<'){
                    stack.push(c);
                } else {
                    if (stack.isEmpty()) {break;}
                    char top = stack.pop();
                    if(c == ')' && top != '(' || c == ']' && top != '[' || c == '}' && top != '{'
                    || c == '>' && top != '<'){
                        break;
                    }
                }
            }

            sb.append("#").append(test_case).append(" ").append(stack.isEmpty() ? 0 : 1).append("\n");

        }

        System.out.print(sb.toString());
    }
}