글 읽기 - [C++]1874번 질문

dlrkddnr2718 1년 전 0

push, pop을 표시하는 부분에는 오류가 없는 것 같은데, 수열을 만들 수 있는지 판단하는 함수에서 오류가 발생하는 것 같습니다. 제가 생각한 것은 1,2,5,3,4에서

5>3처럼 이전 index값이 더 큰 경우가 존재하고, 그 이후에 3,4처럼 연속된 두 수가 나오는 경우 수열을 만들 수 없다고 생각했는데, 이 부분이 틀린 걸까요?

도와주시면 정말 감사드리겠습니다.

#include <iostream>
#include <vector>
using namespace std;
int is_array_avaliable(vector<int>, int); /// 입력받은 배열을 만들 수 있는지를 판단해 주는 함수
int main()
{
    int size = 0;
    cin >> size;
    vector<int> array; /// 배열을 저장할 array vector 선언
    vector<int> LIFO(size); /// int형 vector LIFO 선언.
    vector<int> temp(size); /// 오름차순으로 넣어야 하므로 오름차순으로 정렬해서 넣을 int형 vector 선언.
    for(int i = size; i > 0; i--) /// vector에 오름차순으로 값을 넣어둔다.
    {
        temp.insert(temp.begin(), i);
    }

    for(int i = 0; i < size; i++) /// size 만큼 입력받아서 array에 넣는다.
    {
        int insert = 0;
        cin >> insert;
        array.push_back(insert);
    }
    if(is_array_avaliable(array, size) == -1) /// 배열을 만들 수 없는 경우, no를 출력하고 프로그램을 종료한다.
    {
        cout << "NO" << endl;
        return 0;
    }
    else if(is_array_avaliable(array, size) == 1) /// 배열을 만들 수 있는 경우. 이제 push, pop을 어떻게 해야 하는지를 출력한다.
    {
        for(int i = 0; i < size; i++)
        {
            if(LIFO.front() != array[i]) /// LIFO의 맨 앞과 array의 값이 같지 않은 경우, 같을때까지 push한다.
            {
                while(LIFO.front() != array[i])
                {
                    LIFO.insert(LIFO.begin(), temp.front()); /// LIFO의 맨 앞이 array와 같아질때까지 push하고, push한 수는 temp vector에서 삭제한다.
                    temp.erase(temp.begin()); /// 하나 넣을 때마다, 그 넣은 값은 temp vector에서 제거한다.
                    cout << "+" << endl; /// push 에 해당하는 +를 출력한다.
                }
            }
            cout << "-" << endl; /// if문을 탈출했다면 pop 하면 된다.
            LIFO.erase(LIFO.begin()); /// LIFO의 맨 앞 값을 제거한다.
        }
    }
    return 0;
}
int is_array_avaliable(vector<int> array, int size) /// 배열을 만들 수 있는지를 테스트하는 함수. 만들 수 있으면 1을, 없으면 -1을 반환한다.
{
    int sentinel = 0;
    for(int i = 0; i < size - 1; i++)
    {
        if(array[i] > array[i + 1]) /// 만들어야 하는 배열에서, 크기가 반전된 경우가 있는데, 그 index 뒤에 1,2 같이 연속한 두 수가 나오면 수열을 만들 수 없다. 
        {
            sentinel = i;
            for(int j = sentinel; j < size - 1; j++)
            {
                if((array[j] - array[j + 1]) == -1)
                {
                    return -1;
                }
            }
        }
    }
    return 1; /// for 문을 빠져나왔다면 배열을 만들 수 있는 경우이므로 1을 반환한다.
}

seawon0808 1년 전 1

반례입니다.

반례:
5
3
2
1
4
5
정답:
+
+
+
-
-
-
+
-
+
-
출력: NO

dlrkddnr2718 1년 전 0

감사합니다! 다시 생각해 봐야겠네요 ㅜㅜ

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

문제

문제

출처

ICPC

[C++]1874번 질문

dlrkddnr2718 1년 전 0

seawon0808 1년 전 1

dlrkddnr2718 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말