Baekjoon_1874_스택 수열

문제주소: https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

스택 수열의 문제는 다음과 같습니다.

1. LIFO, FIFO

문제에서 LIFO(Last In First Out)가 언급되며 FIFO(First In First Out)도 함께 언급됩니다.

 

(1) LIFO (Last in First Out) 후입선출

대표적으로 stack이 있으며 리스트의 한쪽 끝에서 데이터의 삽입과 삭제가 이루어지는 자료구조입니다.

가장 최근에 삽입된 자료가 먼저 삭제가 되며 다음과 같은 구조를 갖습니다.

(2) FIFO (First In First Out) 선입선출

대표적으로 queue가 있으며 리스트의 양쪽에서 데이터의 삽입 및 삭제가 가능한 자료구조 입니다.

데이터 구조는 다음과 같습니다.

 

이번 문제는 stack의 개념을 생각하여 풀어낼 것이며 코드는 다음과 같습니다.

Python

import sys

def main():
    i_stack: list = []
    o_stack: list = []
    check_output: int = 0
    count: int = 1

    num_repeat: int = int(sys.stdin.readline()) # 반복횟수 입력

    for i in range(num_repeat):
        my_input: int = int(sys.stdin.readline()) # 숫자 입력

        # 내가 입력한 값이 count보다 크거나 같다면  i_stack과 o_stack에 '+'를 채움.
        while count <= my_input:
            i_stack.append(count)
            o_stack.append('+')
            count += 1

        # 만약 마지막 숫자가 같다면 i_stack의 마지막 숫자를 제거하고 o_stack에 '-'를 채움.
        if i_stack[-1] == my_input:
            i_stack.pop()
            o_stack.append('-')

        # 마지막 숫자가 갖지 않다면, NO를 출력.
        else:
            print('NO')
            check_output = 1
            break

    if check_output == 0:
        for j in o_stack:
            print(j)


if __name__=="__main__":
    main()

 

C++

#include <iostream>
#include <vector>

using namespace std;

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

	vector<int> i_stack;
	vector<char> o_stack;
	int repeat_num;
	int count = 1;
	int my_num;
	int check_output = 1;

	cin >> repeat_num;

	for (int i = 0; i < repeat_num; i++)
	{
		cin >> my_num;
		while (count <= my_num)
		{
			i_stack.push_back(count);
			o_stack.push_back('+');
			count++;
		}

		if (i_stack[i_stack.size()-1] == my_num)
		{
			i_stack.pop_back();
			o_stack.push_back('-');
		}
		else
		{
			cout << "NO";
			check_output = 0;
			break;
		}

	}

	if (check_output == 1)
	{
		for (auto ele : o_stack)
		{
			cout << ele << endl;
		}
	}
}