문제

https://school.programmers.co.kr/learn/courses/30/lessons/76502

---

입력

• 대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s

---

출력

• 올바른 괄호 문자열이 되게 하는 x의 개수

---

풀이

제한조건

• s의 길이는 1 이상 1,000 이하입니다.

접근방법

자료구조 응용

Deque와 Stack의 개념을 이용해서 해결했다.

1. 데크를 이용해서 하나씩 쉬프팅
2. 스택을 이용해서 올바른 문자열인지 확인

위 2과정을 반복하면 정답을 구할 수 있다.

1. 데크를 이용해서 하나씩 쉬프팅
데크(큐)를 선언해주자.
회전하면서 체크해야 하므로, 현재 문자열에 대해서 확인이 종료되면,
가장 앞에 있는 원소를 빼서 가장 뒤로 추가해준다.

Deque<Character> dq = new ArrayDeque();
    public int solution(String s) {
        for(int i = 0; i < s.length(); ++i)
            dq.add(s.charAt(i));
        
        int answer = 0;
        for(int i = 0; i < s.length(); ++i){
            if(isOkay())
                answer++;
            dq.addLast(dq.pollFirst());
        }
        return answer;
    }

2. 스택을 이용해서 올바른 문자열인지 확인
올바른 쌍을 찾는것은 스택을 이용해서 해결할 수 있다.

- 현재 문자열이 여는 괄호인가?
- 현재 문자열과 스택의 Top이 쌍이 맞는가?
- 스택이 비어있는 상태에서 닫는 괄호가 나왔는가?
- 문자열의 끝가지 탐색하였으나, 스택에 문자가 남았는가?

위의 4가지 항목을 분기 조건으로 두고 탐색하면 된다.

---

코드

import java.util.*;

class Solution {
    Deque<Character> dq = new ArrayDeque();
    public int solution(String s) {
        for(int i = 0; i < s.length(); ++i)
            dq.add(s.charAt(i));
        
        int answer = 0;
        for(int i = 0; i < s.length(); ++i){
            if(isOkay())
                answer++;
            dq.addLast(dq.pollFirst());
        }
        return answer;
    }
    
    // 올바른 괄호열인지 체크
    public boolean isOkay(){
        Deque<Character> s = new ArrayDeque();
        for(char c : dq){
            if(isOpen(c)){
                s.addLast(c);
                continue;
            }
            if(s.isEmpty())
                return false;
            if(!isPair(s.peekLast(), c))
                return false;
            s.pollLast();
        }
        if(!s.isEmpty())
            return false;
        return true;
    }
    
    // 쌍이 유효한지 확인
    public boolean isPair(char a, char b){
        if(a == '[' && b == ']')
            return true;
        if(a == '{' && b == '}')
            return true;
        if(a == '(' && b == ')')
            return true;
        return false;
    }
    
    // 여는 괄호인지 확인
    public boolean isOpen(char c){
        if(c == '[' || c== '{' || c== '(')
            return true;
        return false;
    }
}