글 읽기 - 4949번 반례

qocn9029 4년 전 0

여러 수정끝에 예제를 비롯한 여러 케이스 입력해 보았는데 반례를 못찾고 있습니다.

스택을 사용하여 열린 괄호는 무조건 푸쉬하고 닫힌 괄호가 나올경우 top을 조사하여 짝이 현재 s의 원소와 짝이 맞을 경우 pop을 하는 식으로 해서

문자열을 다 돌았을때 스택이 비어있을경우 yes를 출력하도록 했습니다.

예외처리로 스택이 비어있는 경우에 닫힌 괄호가 나온 경우 따로 변수를 두어서 no가 출력 되게금 했습니다.

제가 문제를 잘못 이해한건지; 도저히 반례가 안나오네요

스택이 비어있는데 한번이라도 닫힌 괄호가 나오거나 스택이 비어있지 않은 경우에 no를 출력하고

스택이 비어있고 동시에 스택이 비어있는데 닫힌 괄호가 한번 이라도 나오지 않은 경우 2가지를 모두 만족할때 yes를 출력하도록 했습니다.

도와주시면 감사하겠습니다.

#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main(){

	while(1){
		string s;
		int dis=0;
		getline(cin,s);

		if(s.size()==1 && s[0]=='.') break;

		else{
			
			stack<char> k;

			for(int i=0;i<s.size();i++){

				if(s[i]=='(' || s[i]=='['){
					k.push(s[i]);
				}

				//===================================

				else if(s[i]==')' || s[i]==']'){//런타임 에러를 방지하기 위해 스택이 비어있는 경우와 비어있지 않은 경우를 나눔 
					if(k.empty()){//스택이 비어있는데 닫힌 괄호가 한번이라도 나온 경우 
						dis=1;
					}

					else{
						if(s[i]==')'){
							if(k.top()=='(') k.pop();
						}

						else if(s[i]==']'){
							if(k.top()=='[') k.pop();
						}
					}
				}
			}

			if(k.empty() && dis==0) cout<<"yes"<<endl;

			else if(!k.empty() || dis==1) cout<<"no"<<endl;
		}

		dis=0;

		//cin.clear();
	}

	return 0;

}

palilo 4년 전 1

잘못된 문자열인지 판별을 하는 방법이

1. ) ] 가 등장했는데 스택이 비어있는 경우

2. 문자열의 끝까지 검사했는데 스택에 뭔가 남아있는 경우

이 두 가지뿐입니다.

) ] 가 나왔을 때 스택의 탑에 짝이 맞는 ( [가 들어있는지도 확인해야 합니다

반례
[))))]

qocn9029 4년 전 0

감사합니다!

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

문제

문제

출처

ICPC

4949번 반례

qocn9029 4년 전 0

palilo 4년 전 1

qocn9029 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말