글 읽기 - 1874_스택수열 반례 질문

brewers 1년 전 0

혹시 이렇게 모든 경우를 순서대로 검증하지 않고 특정한 경우에 있어서 실행을 멈추고 NO를 띄워야 정답이 되는건가요?

아니면 제 구조는

1. 지금 push될 수가 스택 수열의 수와 같다면 pop

2. push를 끝까지 다했다면 남은 스택을 전체 pop

3. 나머지 경우는 push만

인데 이것 자체가 잘못된걸까요?

혹은

반례가 있을까요?

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

int main(){
    int N;  cin >> N;

    vector<int> order;
    vector<int> stack_order;
    for(int i=0; i<N; i++){
        int temp;   cin >> temp;
        order.push_back(temp);
    }
    
    //order벡터의 인덱스를 고정시키기 위한 변수
    int order_count = 0;
    
    stack<int> stk;
    stack<char> ans;
    for(int i=1; i<N+1; i++){
        //끝까지 도달했다면 모든 스택을 POP해야한다.
        if(i == N){
            stk.push(i);
            ans.push('+');
            while(stk.size() != 0){
                ans.push('-');
                stack_order.push_back(stk.top());
                stk.pop();
            }
            break;
        }
        //push하는 수와 스택수열의 수가 같다면 출력을 시작
        else if(i != N && i == order[order_count]){
            stk.push(i);
            ans.push('+');
            stack_order.push_back(stk.top());
            stk.pop();
            ans.push('-');
            order_count++;
            int inner_i = i - 1;
            while(inner_i == order[order_count] && stk.size() != 0){
                ans.push('-');
                stack_order.push_back(stk.top());
                stk.pop();
                order_count++;
                inner_i--;
            }
        }
        //push하는 수와 스택수열의 수가 일치하지 않는다면 push만 함
        else{
            stk.push(i);
            ans.push('+');
        }
    }

    //NO를 분간하는 bool변수
    bool can_it_run = true;
    for(int i=0; i<N; i++){
        if(order[i] != stack_order[i]){
            can_it_run = false;
            break;
        }
    }
    
    stack<char>ans_ans;
    if(can_it_run){
        while(ans.size()!=0){
            char temp = ans.top();
            ans_ans.push(temp);
            ans.pop();
        }
        while(ans_ans.size() != 0){
            char temp = ans_ans.top();
            cout << temp << "\n";
            ans_ans.pop();
        }
    }
    else{
        cout << "NO";
    }
}

brewers 1년 전 0

꼭 스택수열과 지금 오름차순으로 올라가고 있는 수가 만나지 않아도 pop될 수 있는 부분을 놓쳤습니다.

if(stk.size() != 0)
    while(stk.top() == order[order_count] && stk.size() != 0){
        ans.push('-');
        stack_order.push_back(stk.top());
        stk.pop();
        order_count++;
        if(stk.size() == 0)
            break;
    }

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

문제

문제

출처

ICPC

1874_스택수열 반례 질문

brewers 1년 전 0

brewers 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말