[자료구조] 백준 문제 풀이 - 1874 스택수열

문제 설명이 애매모호 해서 더러운 문제
+
애초에 끝까지 문제이해를 잘못해서 결정적인것을 못봤을수도...

[문제이해]

BOJ 1874번 스택 수열 - YouTube

[나의코드]

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

int max_arr(int arr[], int num)
{
	int max=0;
	int result;
	for(int i=0; i<num; i++)
	{
		if(max<arr[i])
		{
			max=arr[i];
			result=i;
		}	
	}
	return result;
}

int yes_or_no(int * arr, int num)
{
	int result=0;
	for(int i=max_arr(arr, num)+1; i<num; i++)
	{
		if(arr[i-1]<arr[i])
			result=1;
	}
	return result;
}

int main()
{
	int n;
	cin>>n;
	int max=0;
	stack <int> s;
	int arr[n];
	
	for(int i=0; i<n; i++)
	{
		cin>>arr[i];
	}
	int current=-1;
	
	if(yes_or_no(arr,n))
	{
		cout<<"NO"<<endl;
		exit(1);
	}
	
	
	for(int i=0; i<n; i++)
	{
		if(s.empty())
		{
			for(int j=1; j<=arr[i]; j++)
			{
				s.push(j);
				cout<<"+"<<endl;
			}
			s.pop();
			cout<<"-"<<endl;
			current=arr[i];
			max=arr[i];
		}
		else
		{
			if(current<arr[i])
			{
				if(max<arr[i])
				{
					for(int k=max+1; k<=arr[i]; k++)
					{
						s.push(k);
						cout<<"+"<<endl;
					}
					s.pop();
					cout<<"-"<<endl;
					max=arr[i];
					current=arr[i];
				}
				else
				{
					cout<<"NO"<<endl;	
				}
			}
			else if(current>arr[i])
			{
				for(int j=current; j<=arr[i]; j--)
				{
					s.pop();
					cout<<"-"<<endl;
				}
				s.pop();
				cout<<"-"<<endl;
				current=arr[i];
			}
			else
				exit(1);
		}	
	}
}

 

[다른사람의 코드1]

 

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

int main() 
{
    char sol[200050]; //여기에 +, -값을 모두 저장
    int solptr(0); // +, - 값의 갯수
    int n, x, max(0);
    cin >> n;
 
    stack<int> s;
    while (n--) {
        cin >> x;
        if (x>max) {
            for (int i = max + 1; i <= x; i++) {
                s.push(i);
                sol[solptr++] = '+';
            }
        }
        else
            if (s.top() != x) {  // *여기가 진짜 소름돋는 부분*
                cout << "NO";
                return 0;
            }
        s.pop();
        sol[solptr++] = '-';
        if (max < x) 
			max = x;
    }
    for (int i = 0;i < solptr;i++) cout << sol[i] << "\n";
 
    return 0;
}

[내가 놓친 부분] -> 이걸 생각하는게 대단하다

max보다 작은 x가 들어오면 그 x는 stack.top()과 같은 숫자여야한다. 아닌 경우에는 반복 종료.

      ex) 4,3,6이 입력으로 들어왔으면, x는 5여야한다.

[신기한 부분]

while문을 사용하여 n--하니까 n이 다 소모되면 0이 되어서 while 문이 끝난다

 

 

[다른사람 코드 2]

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

int main()
{
    stack<int> st;
    string op;
    int i = 1; //나의 max 값과 같음
    int n;
    cin >> n;

    while (n--)
    {
        int num;
        cin >> num;

        if (i <= num)
        {
            while (i <= num)
            {
                st.push(i);
                op += '+';
                i++;
            }
            st.pop();
            op += '-';
        }
        else
        {
            if (st.top() < num) //다른사람 코드에서도 내가 놓친부분
            {
                cout << "NO\n";
                return 0;
            }
            else
            {
                st.pop();
                op += '-';
            }
        }
    }
    for (int j = 0; j < op.length(); j++)
    {
        cout << op[j] << "\n";
    }
    return 0;
}

 

결론 -> 이 문제는 목표 숫자까지 다 숫자를 쌓고 목표 숫자만 빼내기 때문에 + max가 나온뒤에 다시 값이 커질수가 없기 때문에 (무조건 계단식으로 낮아져야함) = 그 밑에 숫자들은 아직 안나온 숫자들이다. (s.top<num)의 조건이 가능!!!

[출처]

https://minyeok2ee.gitlab.io/boj/boj-1874/

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

https://kyunstudio.tistory.com/43

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