[BaekJoon 1874][⚪2] 스택 수열

❓ 문제

백준 1874 - “스택 수열”

🎯 난이도

Silver ⚪2

🧠 풀이

1. 내 풀이 (스택)

- 알고리즘

• Data Structure, stack

- 설명

stack를 사용하는 풀이이다.

매번 입력을 받고 'stack'의 다음에 들어올 숫자를 갱신해나가며 적절한 분기로 'push', 'pop'을 해주는 방식이다.

추가적으로 string을 써서 출력을 최적화하고, top을 쓰기 전 empty로 예외 상황을 배제하는 식의 코드를 써주는 식의 안전한 코딩을 해주었다.

N이 단조 증가로 최대 1 ~ N 까지의 반복을 하기 때문에 시간 복잡도는 O(N)이다.

- 코드

내 풀이 코드

#include <iostream>

#include <stack>

#include <string>


using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int iN{};
    cin >> iN;

    stack<int> stNumber{};
    int iNextPush{ 1 }; // 스택에 다음에 push할 숫자

    string strOut{};    // 출력용 문자열
    strOut.reserve(iN * 2);

    while(iN--)
    {
        int iInput{};
        cin >> iInput;

        // 다음 숫자가 iInput보다 작거나 같으면
        while(iNextPush <= iInput)
        {
            stNumber.push(iNextPush++); // 스택에 push하면서 다음 숫자 증가
            strOut += "+\n";
        }

        // 스택 비어있지 않고 맨 위의 요소가 iInput과 다르면 불가능
        if(!stNumber.empty() && stNumber.top() != iInput)
        {
            cout << "NO";
            return 0;
        }
        
        stNumber.pop();
        strOut += "-\n";
    }

    cout << strOut;

    return 0;
}

---

💭 후기

문제 자체는 어렵지 않지만, 반복문 내에서의 분기를 어떻게 처리하느냐에 따라 실행 시간을 최대한 최적화가 가능하다. 문자열로 출력까지 최적화 할 수 있는 것은 덤.

참고로 큰 분류로 봤을땐 stack 문제이지만 푸는 방식 자체는 매 순간 'push', 'pop' 중 하나를 선택하고 한 번 선택하면 돌아갈 수 없는 최적의 해라는 것이 전제이므로 그리디 알고리즘이라고도 볼 수 있다. 그 중에서도 스택 내의 계속해서 변화하는 상태를 추적하며 구현하는 것이므로 그리디 시뮬레이션이라고 하는 것이 가장 알맞다.