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

풀이

 

제목에 나온대로 스택을 이용하여 풀어야 하는 문제이다. 문제에 대한 이해는 해당 문제 홈페이지의 힌트를 보면 어느정도 감이 잡히니 그것을 읽어보자. 이 문제의 경우 소스코드를 바탕으로 풀이하는게 좋을 것 같아서 먼저 소스코드를 첨부한다.

 

소스코드는 다음과 같다.

 

#include <iostream>
#include <string>
#include <vector>

template <typename S>
class Stack {
private:
	std::vector<S> s;
public:

	void Push(S data) {
		s.push_back(data);
	}

	S Pop() {
		if (s.size() == 0) {
			return S(-1);
		}
		else {
			S temp = s[s.size() - 1];
			s.pop_back();

			return temp;
		}
	}

	int GetSize() {
		return (s.size());
	}

	int IsEmpty() {
		if (s.size() == 0)
			return 1;
		else
			return 0;
	}

	S GetTop() {
		if (IsEmpty())
			return S(-1);
		else
			return s[s.size() - 1];
	}
};


int main() {

	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	int n;
	std::cin >> n;

	std::vector<char> v;
	Stack<int> int_stack;

	int i = 0;
	int j = 0;
	int input;

	while (j < n) {
		std::cin >> input;
		while (int_stack.GetTop() < input) {
			++i;
			int_stack.Push(i);
			//std::cout << '+' << std::endl; //디버깅용
			v.push_back('+');
		}

		if (int_stack.GetTop() == input) {
			int_stack.Pop();
			//std::cout << '-' << std::endl; //디버깅용
			v.push_back('-');
		}
		j++;
	}

	if (int_stack.GetTop() != -1) {
		std::cout << "NO\n";
	}
	else {
		for (int k = 0; k < v.size(); k++) {
			std::cout << v[k] << "\n";
		}
	}
}

 

조금 길긴 한데 사실 스택 함수 정의를 제외한다면 그리 코드가 길지는 않다.

 

이 코드에서의 핵심은 int i, j 변수이다. 각각의 역할을 정의하면

 - i : 현재 스택에 들어가야 하거나 들어간 수

 - j : 입력 횟수 

 

따라서 처음 반복문의 조건은 입력횟수가 n번보다 작아야 하는 것이다. 다음 반복문에 들어가기 전, 먼저 입력을 받게 되며, 이 입력을 바탕으로 다음 반복문의 조건을 설정한다. 이 때, 조건은 스택의 마지막 요소가 입력보다 작을 경우에만 참이 되도록 하며, 이 때 스택에 push(i)연산을 진행하게 되며 i의 값이 계속 증가 된다. 

 

if 문의 조건의 경우 스택의 마지막 요소가 input과 같을 경우 pop 연산을 진행하게 된다.

 

이중 루프를 빠져 나오면 스택이 비어있는지 검사를 하게 된다. 왜냐하면 수열을 형성할 수 없다면 스택에는 잔여 요소들이 남게 되기 때문이다. 따라서 스택이 비어있지 않으면 NO를 출력하고 스택이 비어있다면 따로 저장해 놓은 문자열 배열을 출력한다.

 

지금 생각난건데 굳이 +/- 를 저장할 배열을 굳이 vector로 선언하지 않고 char v[2*n]으로 설정해도 될 것 같긴 하다..

코드 순서나 반복문의 조건을 잘 설정해줘야 했기 때문에 꽤 까다로운 문제였다고 생각한다.