B0J 1874 스택수열

 

먼저 해당 문제의 로직이다

이렇게 스택의 성질을 이용해서, 스택 배열을 구현하거나, STL stack을 이용하면 비교적 쉽게 풀린다.

하지만..! 나는 '스택'이란 것 자체를 이용하지 않고 이문제를 풀어보고싶었다( ?!?) 그래서 두가지의 소스코드가 나왔다.

일단 스택을 이용한 소스코드이다. 매우간결하다

 

 

 

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

vector<char>ans;

int main(void) {
	int n;
	int num;
	cin >> n;
	stack<int> s;
	int j = 1;
	for (int i = 0; i < n; i++) { 
		cin >> num;
		if (s.empty() || s.top() < num) { //stack이 empty거나, top 보다 큰 수가 들어온 경우
			for (; j <= num; j++) {
				s.push(j);
				ans.push_back('+');
			}
			j = num + 1;
		}
		if (s.top() != num) { 
			cout << "NO" << endl;
			return 0;
		}
		else if (s.top() == num) {
			ans.push_back('-');
			s.pop();
		}
	}
	for (auto it : ans) printf("%c\n", it);
}

 

 

그리고 아래는 스택을 안쓴 코드이다. 스택을 안썼기때문에 기록을 해야해서 두가지의 큰 크기의 배열생성이 불가피했다.

여기서 char stack 동적배열은, '+'와 '-'의 결과를 저장해주기 위함이다.

 

#include <iostream>
#include <cstdio>
using namespace std;
int seq[100001]; //수열저장
int num[100001] = { 0, }; //요소별로 팝 여부 

int main(void) {
	int n;
	bool able = true;
	scanf("%d", &n);
	char* stack = new char[n * 2+1];
	for (int i = 0; i < n; i++) {
		scanf("%d", &seq[i]);
	} //수열저장

	int j = 0; //seq배열 인덱스   
	int k = 0; //stack 

	for (int i = 1; i <= n; i++) {
		if (seq[j] > i)  // i가 수열의 j요소보다 보다 작은 경우, 일단 다 push를 해준다. 
			stack[k++] = '+'; 
		
		else if (seq[j] == i) { //i가 수열의 j요소와 값이 같은 경우, push 후 pop 
			stack[k++] = '+';
			stack[k++] = '-';
			j++;
			num[i] = 1; //pop
		}

		else if (seq[j] < i) { //i가 수열의 j요소보다 큰 경우
        //가장 최근에 push된 요소를 봐야한다 
			int tmp = 1;
			i--;
			while (1) {
				if (num[(i+1) - tmp]) {
					tmp++; //가장 최근에 push된 요소가 pop되었다면 넘어가주고
					continue;
				}
				else if ((i+1)-tmp == seq[j]) { // 최근에 push된 요소가 j와 같다면 
					stack[k++] = '-';
					num[(i+1) - tmp] = 1;
					j++;
					break;
				}
				else if ((i+1)-tmp!=seq[j]){ //최근에 push된 요소가 j와 같지 않다면
					able = false; //수열생성 불가 
					break;
				}

			}
			if (!able) break;
		}
	}
	j--;
	for (; j < n-1; j++) { //남은요소들 다 넣어주기
    //남은 요소들은 이제 push가 아니라 pop의 대상. 
    //따라서 앞에있는 값 > 뒤에있는 값 이어야 수열 생성가능
		if (seq[j] > seq[j + 1]) stack[k++] = '-';
		else {
			able = false;
			break;
		}
	}


	if (!able)
		printf("NO\n");
	else {
		for (int i = 0; i < k; i++)
			printf("%c\n", stack[i]);
		
	}
	delete[] stack;
	return 0;
}

하하! 스택을 쓰지 않으니 정말 많은 디버깅을 요구했다! 여러 조건들이 필요했기 때문이다!

그래서 나중엔 '역시 스택을 쓰는문제는 스택을 쓰자!'라고 생각이 들었지만서도,

여러모로 공부가 되었다고 생각하기도 한다!