프로그래밍-기본기/알고리즘(문제풀이)

(백준) 1874 스택 수열 C++

독학백수 2023. 9. 11. 10:50
반응형

해당 문제를 이해하기엔 내용이 잘 이해가 되지 않아 접근 방법을 보고 푼 문제이다.
일단 접근 방법에 대해선 그림으로 설명하고 풀이 과정에 대해 설명해보고자 한다.

예시 입력을 그림으로 표현해보았다. 우선 우린 저 배열에서 4가 나올 나올 때 까지 오름차순으로
저 주황색 막대기에 넣어줘야 한다. 

4가 나올 때 까지, Push만을 반복하다가. 4가 나오면 PoP을 해준 뒤 다음 배열에 있는 것을 바라본다.

곧바로 POP을 해주면된다. 이 때, 6을 바라보아야 하는데, 이 때 3과 4는 사용했고 5,6만 들어갈 수 있다.

대충 문제의 접근 방법은 저 그림들로 설명이 가능하다 그럼 이것을 코드로 생각을 해보아야 하는데.

가장 먼저, 어떤 변수들을 사용할 지를 생각해보는 것이다.

Input N, Array,  막대기들이 있을 것이다.

#define MAX 100001
int N;
int Array[MAX];
stack<int> orangeBar;

먼저 N으로 들어올 수 있는 값은 1 이상 100,000 이하 이므로 이를 MAX로 선언해주었고.
Array ( 초록색 막대기 )  orangeBar ( 주황색 막대기 ) 로 만들어 주었다.


Input

void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> Array[i];
    }
}

첫 번째, 입력은 N으로 이후 Array ( 초록색 막대기 ) 에 N 만큼 입력값을 받아둔다.

Solution

int cnt =0;
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        orangeBar.push(i);
        while (orangeBar.empty() == false && orangeBar.top() == Array[cnt])
        {
            orangeBar.pop();
            cnt++;
        }
    }
}

이제 1부터 N까지 OrangerBar에 담아줄 것이다. 
단, While 루프를 돌면서 empty가 false가 아니고, OrangeBar에 맨 마지막이 Array의 cnt인지 확인 후 맞다면.
pop을 해준다. 이후 cnt를 늘려가며 다음 Array(초록색바)의 숫자를 찾아내는 구조로 볼 수 있다.

즉 숫자를 1씩 Push 하면서, 그 숫자가 OrangeBar에 맨 마지막 숫자인지를 검증 한 뒤, 맞다면 pop을 해주고 count를
늘린다.

그럼 위 사진 처럼 4를 찾고 나서 Pop을 다음 숫자가 3이니 숫자를 넣지 않고 또 Pop을 해줄 것이다.

그 다음은 6이니 계속 Push를 할 것인데 이 때 i는 5가 되어 있을 테니 4나 3이 들어갈 일은 없다.

이제 여기서 우리가 출력해야 하는 것이 +, -를 출력해주는 부분을 구현하고 만약 수열을 만들 수 없는 경우엔 NO를
선언해주는 부분을 추가 해주면 된다.

int cnt =0;
vector<char> answer;
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        orangeBar.push(i);
		answer.push_back('+')
        while (orangeBar.empty() == false && orangeBar.top() == Array[cnt])
        {
            orangeBar.pop();
            answer.push_back('-')
            cnt++;
        }
    }
	    if (orangeBar.empty() == false) cout << "NO" << '\n';
    else {
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i] << '\n';
        }
    }
}

여기서 orangeBar가 비어 있지 않으면 수열이 만들어졌다는 것을 의미하므로 NO를
만약 그렇지 않다면 answer에 저장된 값을 하나하나 출력해주므로 문제를 풀 수 있다.

전체 소스 코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <list>
#include<stack>
using namespace std;

#define MAX 100'001

int N;
int arr[MAX];
int cnt = 0;
stack<int> s;
vector<char> answer;

void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
    }
}


void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        s.push(i);
        answer.push_back('+');
        while (s.empty() == false && s.top() == arr[cnt])
        {
            s.pop();
            answer.push_back('-');
            cnt++;
        }
    }
    if (s.empty() == false) cout << "NO" << '\n';
    else {
        for (int i = 0; i < answer.size(); i++)
        {
            cout << answer[i] << '\n';
        }
    }
}

void Solve()
{
    Input();
    Solution();

}

int main()
{
    Solve();
}
반응형