스택 - 짝이 맞지 않는 괄호

 

스택 - 짝이 맞지 않는 괄호

 

 

 

문제출저 - 알고스팟 https://algospot.com/judge/problem/read/BRACKETS2

 

 

 

 

 

풀이생각

1. 닫힌 괄호일 때 스택검사

 => 일치하면 pop, 다르면 바로 return false

2. 열린 괄호일 때 push

3. 함수 마지막에서 스택이 비어있다면 잘 끝난것 (true), 남아있다면 잘못된것 (false)

 

 

내 코드

#include <iostream>
#include <stack>
 
using namespace std;
 
 
bool func(string& s) {
    stack<char> st;
 
    int size = s.size();
    for (int i = 0; i < size; ++i) {
        if (s[i] == ')') {
            if (st.empty()) return false;
            if (st.top() == '(') {
                st.pop();
            }
            else {
                return false;
            }
        }
        else if (s[i] == '}') {
            if (st.empty()) return false;
            if (st.top() == '{') {
                st.pop();
            }
            else {
                return false;
            }
        }
        else if (s[i] == ']') {
            if (st.empty()) return false;
            if (st.top() == '[') {
                st.pop();
            }
            else {
                return false;
            }
        }
        else {
            st.push(s[i]);
        }
    }
 
    return st.empty();
}
 
int main() {
    int T;
    string s;
    cin >> T;
 
    while (T--) {
        cin >> s;
        bool res = func(s);
        res ? cout << "YES" << "\n" : cout << "NO" << "\n";
    }
}

 

 

 

 

 

 

 

 

 

 

+) 추가 (시간 줄이는 삽질)

 

 

그런데 전에 푼 두 분은 C++로 4ms가 걸렸고, 나는 C++로 16ms가 걸렸다. 이유를 알아보기로 했다.

 

 

1. 테스트 케이스가 여는괄호부터 검사하는 것이 많아서 차이발생?

 -> 나는 닫는 것부터 검사하는데 두 분은 여는 것부터 검사했음

 결과 => 여는 것부터 검사했으나 똑같이 16ms가 나왔음

 

2. for문 안의 연산을 줄여보자.

 -> 그러나 empty, top, pop 모두 상수시간 연산이기에 줄일 수 있는게 보이지 않음

 

3. main을 고쳐보자.

 -> 함수결과를 변수 res에 대입하는 것과, bool ? : 연산을 if문으로 고쳐봄

 결과 => 16ms

 

4. main에 cin.sync_with_stdio(false); 추가

 결과 => 드디어 4ms 가 나왔다.

 -> 혹시 몰라서 위의 코드(원래 코드)에서 cin.sync_with_stdio(false)를 추가했다.

 결과 => 4ms가 나왔다.

 

 

 

 

cin.sync_with_stdio(false)는 printf나 scanf를 cout과 cin을 동기화시켜주는 것을 비활성화해서, cout과 cin을 써도 빨라진다고 배웠었다. 그런데 이런 차이를 불러올 지는 몰랐다.