1874 스택 수열 by C++

문제

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

이 문제는 문제를 이해하는데에 시간 소요가 길어서 문제설명을 붙이고자 합니다.

stack에 오름차순으로 1, 2, 3, 4, ... 으로 숫자를 push합니다. 이후 pop연산으로 원하는 배열을 만들면 됩니다.

예를 들어 21543을 만들고 싶다면 push 두번을 하면 1, 2가 push되고 pop을 하면 2가 나오고 pop을 한번 더 하면 1이 나옵니다. 다시 push를 하면 3이 push되고 그다음은 4 그다음은 5순으로 push됩니다. 이후 pop을 세번하면 5, 4, 3으로 빠져나와서 원하는 2,1,5,4,3의 배열을 얻을 수 있습니다.

해결한 방법

실제로 stack을 만들어서 실행시켜보고 가능하다면 결과 불가능하다면 NO를 출력하는 코드를 작성하고자 하였습니다.

1. 입력받은 수보다 push했었던 수가 작다면 오름차순으로 stack에 push한다.
2. push했던 수가 입력받은 수와 같거나 커지면 top에 있는 수와 입력받은 수를 비교해서 다르다면 NO를 출력한다.
3, stack으로 구현할 수 있음을 알게되었으니 오류발생 여부는 고려하지 않고 변수(count)를 선언해서 배열의 수가 변수보다 커지면 count++ 실행과 "+"를 출력을 한다.
4. 배열을 인덱싱할때마다 "-"를 출력한다.

이 문제에서 시간 초과가 자꾸 발생했는데 cin을 통한 입력과 cout << endl 을 통한 개행의 시간이 오래걸리는 것이 문제였습니다. 그래서 cin대신에 scanf를 cout << endl 대신에 cout << "\n" 을 사용하여 문제를 해결했습니다. 혹시 시간초과로 틀리시는 분들은 이와 관련한 문제가 아닌지 확인해보세요!

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

int main()
{
	int line_num;
	scanf("%d", &line_num);

	int* li = new int[line_num];
	stack<int> s;
	int count = 0;
	int input_n = 0;
	int i;
	for (i = 0; i < line_num; i++) {
		scanf("%d", &input_n);
		li[i] = input_n;
		while (count < input_n) {
			count++;
			s.push(count);
		}
		if (input_n == s.top()) {
			s.pop();
		}
		else{
			cout << "NO";
			return 0;
		}
	}

	count = 1;
	cout << "+";
	for (i = 0; i < line_num; i++)
	{
		while (count < li[i]) {
			count++;
			cout << "\n+";
		}
		cout << "\n-";
	}
	delete[] li;
    return 0;
}

개선한 방법

1. for 문을 두 개를 구성하지 않고 하나의 for문에 string으로 선언한 result에 +, -를 입력한다.
2. stack으로 구현이 불가능하다면 NO를 출력하고 가능하다면 result를 출력한다.

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

int main()
{
	int line_num;
	scanf("%d", &line_num);

	int* li = new int[line_num];
	stack<int> s;
	int count = 1;
    s.push(1);
	int input_n = 0;
	string result = "+";
	int i;
	for (i = 0; i < line_num; i++) {
		scanf("%d", &input_n);
		li[i] = input_n;
		while (count < input_n) {
			count++;
			s.push(count);
			result += "\n+";
		}
		if (input_n == s.top()) {
			s.pop();
			result += "\n-";
		}
		else {
			cout << "NO";
			return 0;
		}
	}
	cout << result;
	delete[] li;
    return 0;
}