글 읽기 - 9012번 질문드립니다.

krlittle 2년 전 1

아래 코드입니다.

첫번째 입력 예시를 넣었을때 전부 NO가 나오는데, 각각의 케이스를 따로따로 입력하면 맞게 출력됩니다.

입력의 문제인듯 한데, 어떻게 하면 될까요?

감사합니다!

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

stack <char> st;

void solve(string s)
{
    if(s[s.size() - 1] == '(') // 만약 string의 마지막 문자가 '('이면 NO
    {
        cout << "NO" << '\n';
        return;
    }

    if(s[0] == ')') // 첫 문자가  ')'이어도 NO
    {
        cout << "NO" << '\n';
        return;
    }

    if(s.size() % 2 != 0) // 문자 개수가 홀수면 쌍을 이룰 수 없으므로 NO
    {
        cout << "NO" << '\n';
        return;
    }

    int cnt1, cnt2; // '('과 ')'의 개수를 세어줄 변수
    cnt1 = 0, cnt2 = 0;

    for(int i = 0; i < s.size(); i++) // 스택에 넣고 각 괄호 개수 세어주는 과정
    {
        if(s[i] == '(' || s[i] == ')') st.push(s[i]);
        if(s[i] == '(')
        {
            cnt1++;
        }
        else if(s[i] == ')') cnt2++;
    }
    if(cnt1 != cnt2) // 괄호의 개수가 다르다면 NO출력
    {
        cout << "NO" << '\n';
        return;
    }

    int cnt = 0;
    while(!st.empty()) // 괄호가 VPS인지 확인
    {
        while(st.top() == ')')
        {
            st.pop();
            cnt++;
            if(st.empty()) break;
        }
        while(st.top() == '(')
        {
            st.pop();
            cnt--;
            if(st.empty()) break;
        }
        if(cnt < 0)
        {
            cout  << "NO" << '\n';
            return;
        }
    }
    cout << "YES" << '\n';
    return;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string s;
        cin >> s; // 입력인데 이 부분에서 공백문자때문에 문제가 생기는 건가요?
        solve(s);
    }
    return 0;
}

djm03178 2년 전 1

매 케이스가 끝날 때마다 st를 비워줘야 합니다.

krlittle 2년 전 1

아래 부분에서 스택이 비워지는 것 아닌가요?

while( !s.empty() ) s.pop();

위 코드 사용해서 solve함수 맨 끝에 스택 비워주었는데도 틀렸다고 뜹니다 ㅠㅠ

    while(!st.empty()) // 괄호가 VPS인지 확인
    {
        while(st.top() == ')')
        {
            st.pop();
            cnt++;
            if(st.empty()) break;
        }
        while(st.top() == '(')
        {
            st.pop();
            cnt--;
            if(st.empty()) break;
        }
        if(cnt < 0)
        {
            cout  << "NO" << '\n';
            return;
        }
    }

djm03178 2년 전 1

함수가 종료되는 시점이 거기에만 있지 않습니다. 42번째 줄에서 끝나는 경우에는 스택에 남는 게 있을 수도 있습니다.

krlittle 2년 전 0

덕분에 해결했습니다.

감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

9012번 질문드립니다.

krlittle 2년 전 1

djm03178 2년 전 1

krlittle 2년 전 1

djm03178 2년 전 1

krlittle 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말