[033] 9012. 괄호

✨ 알고리즘 분류 : 자료구조 / 문자열 / 스택

 

https://www.acmicpc.net/problem/9012

9012번: 괄호

 

 

---

 

 

🪡 문제에서 요구하는 조건 정리

 

 1. 문자열은 두가지 '(' 와 ')' 로 이루어져있다

2. '(' 와 ')' 두가지가 올바르게 짝지어진 상태의 문자열은 YES, 아니라면 NO를 출력한다

 

 

🧶 풀이과정 

 

우선, 주어진 것들 하나씩 deque에 담은 다음, 제일 첫번째 것을 빼낸다.

빼낸 괄호가 '(' 라면, 제일 가까운 곳에 있는 ')'를 삭제하는데 만약 삭제할 ')'가 없다면 이것은 올바른 괄호 문자열이 아니므로 false를 리턴한다.

빼낸 괄호가 ')' 라면, '('괄호랑 짝지어질 수 없기 때문에 false를 리턴한다.

마지막까지 정상적으로 삭제를 완료했으면, 이것은 올바른 괄호 문자열이기 때문에 ture를 리턴한다.

Deque 구조 에 대해 이해하고 있다면, 쉽게 접근하고 풀 수 있다.

 

 

🏹 제출코드

package data_structure_part_01;

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;

public class Q9012 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int t = Integer.parseInt(br.readLine());
        boolean[] b = new boolean[t];
        boolean ck = false;

        for(int i = 0 ; i < t ; i ++){
            String str = br.readLine();
            Deque<Character> deq = new ArrayDeque<>();
            ck = false;
            String e = (i != t-1) ? "\n" : "";

            for(int j  = 0; j < str.length(); j++){
                deq.add(str.charAt(j));
            }

           while(!ck){

               b[i] = true;

               // 덱이 비어있지 않을 경우
               if(!deq.isEmpty()){

                   // 덱의 첫번째 요소를 반환하고
                   char c = deq.poll();

                   // c가 여는 괄호일 경우에
                   if(c == '('){

                       // 현재 덱의 전체 길이를 가져옴
                       int size = deq.size();

                       // 덱의 처음에서부터 찾았을 때 ')'가 존재한다면 지우기
                       deq.removeFirstOccurrence(')');

                       // 현재 덱의 길이와 지운 후 길이가 같다면 ')' 괄호가 없는 것이므로 반복 바로 종료
                       if(size == deq.size()){
                           b[i] = false;
                           break;
                       }
                   // 첫번째가 닫는 괄호일 경우
                   }else{
                       b[i] = false;
                       break;
                   }
               // 덱이 비었을 때
               }else{
                   b[i] = true;
                   break;
               }

           }

          bw.write((b[i] ? "YES"  : "NO") + e );
        }


        bw.flush();
        bw.close();
        br.close();
    }
}