[백준 BOJ] 1874번 스택 수열 (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/1874

1874번: 스택 수열

 

접근 방법 - 스택과 큐를 이용한 문제

백준의 1874번 문제는 스택과 큐를 함께 사용하여 해결할 수 있는 문제이다.

해당 문제는, 1부터 n까지의 숫자가 순차적으로 스택을 거친다고 할 때 입력받은 수열을 생성할 수 있는지의 여부를 묻고 있다.

여기에 덧붙여, 수열 생성이 가능할 시엔 push와 pop의 순서를 출력해야 하며 생성이 불가할 시엔 "NO"를 출력해야 하는 문제이다.

여기서 필자는 수열 생성이 가능할 시에만 push와 pop 순서를 묻는다는 점에서 큐를 함께 사용하였다.

'+' 와 '-' 를 큐에 미리 저장한 다음, 수열 생성이 최종적으로 가능할 시에 순차적으로 출력을 하고 아닐 시엔 출력하지 않는 방법을 택한 것이다.

자세한 설명은 아래의 코드에 대해 설명하면서 덧붙이고자 한다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 입력받는 수열의 길이이자 스택에 push할 숫자의 개수(n)를 입력받는다. 잇따라, 생성하고자 하는 수열을 차례로 입력받는다.

 

2) 스택과 큐를 선언한다.

 

3) k는 1로 초기화하여 선언하고, i는 0으로 초기화하며 선언한다.

(여기서 k는 스택에 순차적으로 push할 숫자이며, i는 1)에서 입력받은 각 수열값을 가리키는 데에 사용되는 제어 변수이다.)

 

4) k가 n보다 커질 때까지, 또는 i가 n과 같아질 때까지 반복문을 실행하며 아래의 연산을 취한다.

(입력받은 수열의 값과 스택의 top값을 동시에 탐색하도록 하였다.)

- 스택이 비어있거나 스택의 top값이 arr[i]와 같지 않다면 k값을 확인한다.

만일 k가 n보다 크다면, 이는 더 이상 스택에 push할 값이 없다는 뜻이며 입력받은 수열을 생성하지 못했다는 뜻이기도 하다.

따라서 이 경우엔 "NO"를 출력하고 즉시 실행 종료하도록 한다.

만일 k가 n보다 작거나 같다면, 아직 스택에 push할 값이 남아있다는 뜻이다.

따라서 이 경우엔 스택에 k값을 push한 뒤, k를 1 증가시킨다. 추가로, 큐에도 '+'를 push한다.

(k를 1 증가시키는 것은 다음 연산에서 스택에 push할 값을 변경하는 것이다.)

- 만일 스택의 top값이 arr[i]와 일치한다면 스택에서 pop 연산을 취한다, 추가로, 큐에도 '-'를 push하며 i를 1 증가시킨다.

(i를 1 증가시키는 것은 다음 연산에서 접근할 수열의 값을 변경하는 것이다.)

 

5) 위 연산이 모두 끝났다면, 큐가 빌 때까지 반복문을 실행하며 아래의 연산을 취한다.

- 큐의 front값을 출력하면서 pop 연산을 취한다. 

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <stack>
#include <queue>
#define endl '\n'
using namespace std;

//백준 1874번 코드
int arr[100000];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

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

	stack<int> s;
	queue<char> c;
	int k = 1;
	int i = 0;
	while (k <= n || i < n) {
		if (!s.empty() && arr[i] == s.top()) {
			s.pop();	c.push('-');
			i++;
		}
		else {
			if (k > n) {
				cout << "NO" << endl;
				return 0;
			}
			s.push(k);	c.push('+');
			k++;
		}
	}

	while (!c.empty()) {
		cout << c.front() << endl;
		c.pop();
	}
}

 

제출 결과

(2022.02.26 백준 1874번 문제 제출 결과)

(스택-큐 병행 생각보다 힘들었다...)