4949 반례부탁드립니다.(질문을 잘못하여 재질문입니다.)

Question

우선 제 로직은 // stk이 비어있는 경우 // ch가 열린 괄호인 경우 // push(ch); // ch가 닫힌 괄호인 경우 // push(ch); break; // stk이 비어있지 않은 경우 // ch가 열린 괄호인 경우 // top()이 닫힌 괄호인 경우 && 형태가 다름 // top()이 닫힌 괄호인 경우 && 형태가 같음 // top()이 열린 괄호 && 형태가 다름 // top()이 열린 괄호 && 형태가 같음 // ==> 위의 4경우 모두 push(ch); // ch가 닫힌 괄호인 경우 // top()이 닫힌 괄호인 경우 && 형태가 다름 // top()이 닫힌 괄호인 경우 && 형태가 같음 // ==> 위의 2경우 모두 push(ch); // top()이 열린 괄호인 경우 // 형태가 다른 경우 // break; // 형태가 같은 경우 // pop(); // stk이 비어있는 경우 // yes // stk이 비어있지 않는 경우 // no 입니다. #include using namespace std; int main(){ string input; getline(cin,input); string ret; while(input!="."){ stack stk; for(int i=0;i 위의 4경우 모두 push(ch); stk.push(ch); } // ch가 닫힌 괄호인 경우 else{ // top()이 닫힌 괄호인 경우 && 형태가 다름 // top()이 닫힌 괄호인 경우 && 형태가 같음 // ==> 위의 2경우 모두 push(ch); if(stk.top()==')'||stk.top()==']'){ stk.push(ch); } // top()이 열린 괄호인 경우 else{ // 형태가 다른 경우 if(stk.top()=='('&&ch==']'){ // break; break; } else{ // 형태가 같은 경우 // pop(); stk.pop(); } } } } } // stk이 비어있는 경우 if(stk.empty()){ // yes ret+="yes "; } // stk이 비어있지 않는 경우 else{ // no ret+="no "; } getline(cin,input); } printf("%s",ret.c_str()); return 0; } 거의 대부분의 반례를 넣어도 통과가 됩니다. 어디서 잘못되었나요?

큰돌 · Answer

안녕하세요 상준님 ㅎㅎ 일단 먼저 코드리뷰를 드리면 코드가 너무 복잡합니다. 1.중복되는 부분이 있습니다. if(ch=='('||ch=='['){ // top()이 닫힌 괄호인 경우 && 형태가 다름 // top()이 닫힌 괄호인 경우 && 형태가 같음 // top()이 열린 괄호 && 형태가 다름 // top()이 열린 괄호 && 형태가 같음 // ==> 위의 4경우 모두 push(ch); stk.push(ch); } 예를 들어 이렇게 되어있는데 // top()이 닫힌 괄호인 경우 && 형태가 다름 // top()이 닫힌 괄호인 경우 && 형태가 같음 // ==> 위의 2경우 모두 push(ch); if(stk.top()==')'||stk.top()==']'){ stk.push(ch); } 그 다음에는 또 push를 하구요. 즉, 어차피 push를 할 건데 불필요한 분기처리가 있습니다. else{ // no ret+="no "; } getline(cin,input); 마지막에 입력받는 부분도 처음에 입력받게 하면 깔끔하게 할 수 있습니다. 마지막으로 틀린 로직입니다. if(stk.top()==')'||stk.top()==']'){ stk.push(ch); } // top()이 열린 괄호인 경우 else{ // 형태가 다른 경우 if(stk.top()=='('&&ch==']'){ // break; break; } else{ // 형태가 같은 경우 // pop(); stk.pop(); } } 상준님 로직은 만약 size가 있다면 -> 균형잡히지 않은 세상을 판단하는 것인데요. top이 ) -> 라면 push를 해서 사이즈가 생기게 한다 -> 맞음 ( 또는 [일 경우 -> ), ]이 만났을 때 제거해야 함. -> 이부분이 틀립니다. if(stk.top() == '(' && ch == ')'){ stk.pop(); }else if(stk.top() == '[' && ch == ']'){ stk.pop(); }else{ break; } 이렇게 고치셔야 합니다. 전체코드는 다음과 같습니다. #include using namespace std; int main(){ string input; getline(cin,input); string ret; while(input!="."){ stack stk; for(int i=0;i 위의 4경우 모두 push(ch); stk.push(ch); } // ch가 닫힌 괄호인 경우 else{ // top()이 닫힌 괄호인 경우 && 형태가 다름 // top()이 닫힌 괄호인 경우 && 형태가 같음 // ==> 위의 2경우 모두 push(ch); if(stk.top()==')'||stk.top()==']'){ stk.push(ch); } // top()이 열린 괄호인 경우 else{ // 형태가 다른 경우 if(stk.top() == '(' && ch == ')'){ stk.pop(); }else if(stk.top() == '[' && ch == ']'){ stk.pop(); }else{ break; } } } } } // stk이 비어있는 경우 if(stk.empty()){ // yes ret+="yes "; } // stk이 비어있지 않는 경우 else{ // no ret+="no "; } getline(cin,input); } printf("%s",ret.c_str()); return 0; } 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.