글 읽기 - 질문게시판의 반례도 모두 정상 처리 확인 하였는데도 틀려서 질문 드립니다.

kbear 4년 전 0

안녕하세요.

문제점을 찾아내려고 질문 게시판에 답변달아주신 반례 들을 다 정상 처리하는데도 틀려서 질문 드립니다.

res 벡터는 결과를 저장하기 위한 벡터로, 마지막 문자의 NGE부터 반대 순서로 결과를 저장합니다. (출력 시 벡터 마지막 위치부터 거꾸로 출력)

입력은 벡터 v 와 스택 s에 모두 저장합니다.

마지막 입력되는 숫자는 항상 NGE 가 -1 일 것이기 때문에 res 벡터에 -1 을 push_back 하고, 입력 숫자들을 순서대로 푸시한 스택 s에서 pop을 한번 수행합니다.

// line 26, 27

그 후 NGE를 계산하기 위해 비교 연산을 통해 각 인덱스에 해당하는 NGE를 계산하도록 하였습니다.

어떤 부분에서 오류가 있는지 제 힘으로 더이상 찾을 수 없어서 도움 요청합니다 ㅠㅠ

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

using namespace std;

int n;
stack<int> s;
vector<int> v;
vector<int> res;
int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    
    cin >> n;
    for(int i=0 ;i<n; i++){
        int temp;
        cin >> temp;
        v.push_back(temp);
        s.push(temp);
    }
    
    
    int len = v.size();
    res.push_back(-1);
    s.pop();
    int max = 0;
    for(int i=len; i>1; i--){
        int nge = -1;
        int cur = v.at(i-1);
        int comp = s.top();

        s.pop();
        if(comp < cur)
            nge = cur;
        else if(!res.empty() && res.at(len-i) > comp)
            nge = res.at(len-i);
        else if(comp < max)
            nge = max;
   
        
        if(max < nge) max = nge;
        res.push_back(nge);
    }
        
    for(int i=len; i>0; i--){
        cout << res.at(i-1) << " ";
    }
    cout << "\n";
    
    
    
    return 0;
}

pichulia 4년 전 2

지나가다 댓글도 없고 아직 못푸셨길래 댓글 달아봅니다.

의외로 논리가 괜찮아서 깜빡 속을 뻔했지만

39,40번째 줄에 대한 논리가 부족합니다.

여기 좋은 반례가 있습니다....

덤으로 지금 스택을 쓰신 이유가 전혀 없는것 같습네다. comp값은 결국 v.at(i-2)랑 똑같으니까요

5
3 1 2 4 5

kbear 4년 전 0

답변 정말 감사합니다!

조언해주신 부분이 확실히 문제였습니다!

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

문제

문제

출처

ICPC

질문게시판의 반례도 모두 정상 처리 확인 하였는데도 틀려서 질문 드립니다.

kbear 4년 전 0

pichulia 4년 전 2

kbear 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말