[BOJ알고리즘, C++]#1874_스택 수열, 선형 자료구조, 스택

 

[BOJ알고리즘, C++]#1874_스택 수열, 선형 자료구조, 스택

 

BOJ 알고리즘 문제 풀이, 1874번 스택 수열

선형 자료구조 중 스택을 활용해 수열을 나타냅니다.

 

---

 

 

Overview

 

1. 문제
2. 풀이
3. 코드

 

#0. 문제

1. 문제

 

#1. 풀이

1. 스택

[자료 구조]#0_선형 자료구조

 

• 선형 자료구조는 데이터를 일렬로 저장하고 관리하는 자료구조로, 각 데이터는 앞이나 뒤에 위치한 데이터와 연결되어 있습니다. 그리고, 선형 자료구조는 논리적 순서와 물리적 순서가 일치합니다.
• 그중 스택은 후입선출 혹은 LIFO(Last In First Out) 방식으로 동작하는 전혀 자료구조입니다.
• 스택은 같은 구조와  같은 크기의 데이터를 정해진 하나의 방향으로만 삽입/삭제가 이루어지며, top(가장 마지막으로 삽입된 항목)으로 정해진 곳으로만 접근이 가능합니다.

 

2. 스택의 활용

• 먼저, 우리는 1부터 N까지의 숫자를 스택에 넣거나, 혹은 빼는 동작을 통해 하나의 수열을 만들어야 합니다.
• 입력받은 숫자를 스택에서 꺼내는 동작을 위해 우리는 해당 숫자를 먼저 스택에 넣는 동작이 필요합니다. 그리고, 해당 숫자가 스택의 top 혹은 마지막 들어온 숫자가 되기 위해 해당 숫자 이전의 숫자들을 스택에 지속적으로 push 해주어야 합니다. 따라서, 우리는 1부터 N까지의 숫자 중 현재 어떤 숫자가 스택에 마지막으로 들어온 숫자(top)인지 기억해야 하며, "NO"가 되는 조건을 파악해야 합니다.
• 우선, count 변수가 입력받은 숫자 A보다 작은지 체크합니다. count 변수가 A보다 작다면, count 변수가 A가 될 때까지 push 동작을 수행합니다(A가 4고 count 변수가 0이라면, 0 ~ 4까지의 숫자들을 차례대로 스택에 push 합니다). 만약, 숫자 A가 count 변수와 같다면, 이는 곧 스택의 top이 숫자 A라는 뜻이며, 스택의 pop 동작을 수행합니다.
• 이때, count 변수가 숫자 A보다 크다면, 숫자 A는 스택의 top()이 아니라, 그 밑에 깔려있는 숫자임을 의미하며, 최종적으로 해당 수열은 스택을 통해 표현할 수 없음을 의미합니다!

 

#2. 코드

1. 1874번 제출 코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int n, a;

int main()
{
    cin >> n;
    
    stack<int> s;
    vector<char> v;
    // #1. count 변수, 스택에 들어있는 마지막 숫자를 기억합니다.
    int cnt = 1;
    
    for(int i=0; i<n; i++)
    {
        cin >> a;
        // #2. 숫자 a가 스택의 마지막 숫자보다 크다면, cnt변수가 a가 될때까지 push 수행
        while(cnt <= a)
        {
            s.push(cnt);
            cnt++;
            v.push_back('+');
        }
        // #3. 스택의 마지막 숫자가 a와 같다면, pop동작 수행
        if(s.top() == a)
        {
            s.pop();
            v.push_back('-');
        }
        // #4. 스택의 마지막 숫자가 a보다 크다면, "NO" 출력
        else
        {
            cout << "NO";
            return 0;
        }
    }
    
    for(auto c : v)
    {
        cout << c << '\n';
    }
    
}

 

Details

 

1. 먼저, 스택의 마지막 숫자를 기억하기 위해 별도의 정수 cnt를 정의합니다.
2. 입력으로 들어온 숫자 a가 cnt 변수보다 크다면, cnt ~ a의 숫자들을 모두 스택에 push 합니다.
3. 입력으로 들어온 숫자 a가 cnt 변수와 같다면, pop 동작을 수행합니다.
4. 입력으로 들어온 숫자 a가 cnt 변수보다 작다면, 수열을 표현하는 것이 불가능하므로 "NO"를 출력하고 종료합니다.