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

문제 링크

---

1874번: 스택 수열

접근 방법

---

1. 1부터 n까지의 수를 스택에 삽입해야 하므로 stack을 사용합니다.
2. 사용한 연산을 순서대로 출력하기 위해 queue를 사용합니다.

소스 코드

---

#include <iostream>
#include <queue>
#include <stack>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	queue<string> op; // 사용한 연산을 넣을 큐입니다.
	stack<int> sequence; //1부터 n까지의 수를 넣을 stack입니다.
	int num, t, i = 0;

	sequence.push(0);
	cin >> t;

	while (t--)
	{
		cin >> num;
		if (sequence.top() < num) //입력받은 값이 스택에 있는 값보다 크면
		{
			while (i < num) // 같아질 때까지 스택에 삽입합니다.
			{
				sequence.push(++i);
				op.push("+");
			}
		}

		if (sequence.top() == num) // 스택에 있는 값과 같다면
		{
			op.push("-"); 
			sequence.pop();
		}
		else //스택에 있는 값이 입력받은 값보다 크다면 수열을 만들지 못합니다.
		{
			cout << "NO";
			return 0;
		}
	}

	while (!op.empty()) // 큐에 들어있는 연산들을 출력합니다.
	{
		cout << op.front() << '\n';
		op.pop();
	}

	return 0;
}

코드 설명

---

변수

push연산과 pop연산을 사용한 순서대로 저장하기 위해 queue를 사용했습니다.

스택을 이용해 해당 수열을 만들 수 있는지 확인하는 문제이기 때문에, stack을 사용했습니다.

시행 횟수를 받는 변수 t, 스택에 넣을 숫자를 저장하는 변수 i, 수열을 구성하는 정수를 받는 변수 num을 사용했습니다.

 

코드

수열의 값이 스택에 가장 나중에 들어온 값보다 크면 값이 같아질 때까지 스택에 오름차순으로 값을 넣어줍니다.

스택에 push연산을 할 때마다 큐에 '+'를 삽입합니다.

수열의 맨 처음의 값이 1일 수 있기 때문에 stack.top을 0으로 초기화하여 1이 들어왔을 때 스택에 1을 삽입할 수 있도록 해주었습니다.

스택에 있는 값이 입력받은 값과 같으면 스택에서 pop을 해주며 큐에 '-'를 삽입합니다.

만약 스택에 있는 값이 입력받은 값보다 크면 해당 수열을 만들 수 없기 때문에 NO를 출력하고 종료합니다.

위 과정을 반복해 수열을 만드는 과정이 끝나면, 수열을 만드는데 사용했던 연산들을 순서대로 출력합니다.

 

스택으로 수열을 만들 때 스택에 들어있는 값을 문제의 예제입력 1로 보여드리겠습니다.

num == 4 일 때

0

1

2

3

4

num == 3 일 때

0

1

2

3

num == 6 일 때

0

1

2

5

6

num == 8 일 때

0

1

2

5

7

8

num == 7 일 때

0

1

2

5

7

num == 5 일 때

0

1

2

5

num == 2 일 때

0

1

2

num == 1 일 때

0

1