[C++]백준 1874번 - 스택 수열

---

0. 문제

 

https://www.acmicpc.net/problem/1874

1. 아이디어

 

1) "1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써" 라는 문장을 보면

수열을 구성하는 값들은 스택에 PUSH 되고 POP 되는 과정을 한 번씩 거쳐야 한다는 걸 알 수 있다.

 

2) 우선, 스택이 비어있다면 넣고자 하는 값까지의 수들을 오름차순으로 스택에 PUSH 하면 된다.

(물론 같은 정수가 두 번 나오는 일은 없으니 그것 또한 함께 체크해줘야 한다)

 

3) 값(input)이 스택의 top()과 같다면, 고민할 필요 없이 POP을 해서 꺼내 주면 된다.

 

4) 값(input)이 스택의 top() 보다 크다면, 현재 top()의 다음 값부터 input까지를 스택에 PUSH 하고

마지막에 POP을 한번 해주면 원하는 값을 얻을 수 있다.

 

5) 그리고 값이 스택의 top() 보다 작다면, 해당 값이 이미 스택 안에 들어있다는 소리인데

스택은 출입구가 하나이므로 그 값을 꺼내기 위해 몽땅 뒤집어야 한다.

꺼내고 나면 다시 PUSH 할 순 없으니 올바른 결과가 나오지 않는다. 따라서 input <top()이면 "NO"를 출력하면 된다.

 

2. 소스코드

 

#include <iostream>
#include <stack>
char result[200000] = { 0 };
void stkpop(std::stack<int>& stk, bool* array ,int& pos, char* result)
{
    array[stk.top()] = true;
    stk.pop();
    result[pos++] = '-';
}
void stkpush(std::stack<int>& stk, int& num, int& pos, char* result)
{
    stk.push(num);
    result[pos++] = '+';
}
int main()
{
    std::stack<int> st;
    int N;
    std::cin >> N;
    bool* arr= new bool[N + 1]; // 출력여부를 기록할 배열
    for (int i = 1; i <= N; i++)
        arr[i] = false;
    int index = 0;
    bool possible = true;
    for (int i = 0; i < N; i++)
    {
        int input;
        std::cin >> input;
        if (st.empty())
        {
            for (int i = 1; i <= input; i++)
            {
                if (arr[i] == false) {
                    stkpush(st, i, index, result);
                }
            }
            stkpop(st, arr, index, result);
        }
        else if (input == st.top())
        {
            stkpop(st, arr, index, result);
        }
        else if (st.top() < input)
        {
            for (int i = st.top() + 1; i <= input; i++)
            {
                if (arr[i] == false)
                {
                    stkpush(st, i, index, result);
                }
            }
            stkpop(st, arr, index, result);
        }
        else if (input < st.top()) possible = false;
    }
    delete arr;
 
    if (possible) {
        for (int i = 0; result[i] != 0; i++)
            std::cout << result[i] << '\n';
    }
    else std::cout << "NO";
}

 

3. 결과

 

4. 피드백

 

• 시간이 너무 많이 걸린다...
• 출력여부를 확인하는데 FOR문을 돌리니까 처음에는 시간초과가 떴다. 어거지로 BOOL 배열을 만들어서 풀어내긴 했는데 문제가 원하는 답과는 거리가 먼 듯 하다..
• 동적할당된 BOOL 배열을 memset 함수로 초기화시키려다 시간을 많이 잡아먹었다. (안되는거였음)
• PUSH와 POP 될 때 공통적으로 실행되는 부분을 함수로 만드는데 헷갈렸다. 포인터나 레퍼런스에 대한 이해가 부족한 것 같다. 공부를 더 꼼꼼히 해야겠음.
• PUSH와 POP이 될 때마다 '+'나 '-'를 출력하게하니까 NO인 경우에 출력초과가 떴다. 출력조건 확인!

---

TO DO LIST: 포인터, 레퍼런스

---