백준 1874번 : 스택 수열

문제 접근

---

1. 원하는 수열의 확인해야 되는 부분과 스택의 top을 비교한다.
2. 값이 같다면, 스택을 pop 하고 정답에 '-'를 추가한다.
3. 값이 다르다면, 증가하는 정수 값을 스택에 push하고 정답에 '+'를 추가한다.
4. 증가하는 정수 값이 n보다 큰데, 접근 1의 비교 값이 다르다면 수열이 만들어질 수 없으니 "NO"를 출력한다.

 

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

1874번: 스택 수열

 

 

 

문제 코드

---

#include <iostream>
#include <vector>

using namespace std;

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

	int size, input_flag = 0, inc_seq = 1;
	vector<int> input, stack;
	vector<char> result;

	cin >> size;
	input.resize(size);

	while (input_flag != size)
		cin >> input[input_flag++];

	input_flag = 0;

	while (input_flag != size)
	{
		if (!stack.empty() && stack.back() == input[input_flag])
		{
			result.push_back('-');
			stack.pop_back();
			++input_flag;
		}

		else if (inc_seq <= size)
		{
			stack.push_back(inc_seq++);
			result.push_back('+');
		}

		else
			break;
	}

	if (stack.empty())
		for (auto iter : result)
			cout << iter << '\n';
		
	else
		cout << "NO\n";

	return 0;
}

 

 

 

느낀 점

---

    알고리즘 레콩키스타에서 처음으로 풀이할 것으로 선정한 문제다. 확실히 머리가 초기화됐다는 게 느껴지긴 하는데, 그만큼 빨리 감각을 회복할 수 있을 것 같다. 솔직히 회복해도 문제만 조금 풀어본 정도라 코드포스 같은데서는 민트도 안 된다. 따라서 레콩키스타는 회복뿐만 아니라 성장까지 겸하는 프로젝트로 생각하려고 한다.

 

2023 알고리즘 레콩키스타 - 시작

 

    레콩키스타의 목표도 조금 바뀔 것 같다. 알고리즘을 오랜만에 하기에 머리 아플 줄 알았는데 생각보다 재미있었고, 2주동안 알고리즘이 아닌 이전의 글들을 정리하는 시간을 보냈기에 기존 목표는 아마 달성하기 어려울 것으로 보인다. 일단은 2월뿐만 아니라 꾸준히 진행하는 프로젝트로 생각해야 될 것 같다.

 

    이번 문제 풀이에서 느낀 점을 끝으로 풀이 후기를 마치겠다.

 

 

1. 문제를 풀이하며, 조건을 보고, 확실한 기준을 만들자.
   
     이번에 증가하는 정수, 원하는 수열, 스택 등 어떤 것을 기준으로 삼을지 확실히 정하지 않아 시간이 조금 지체됐다.
   
   
2. 값을 변화시키는 부분의 유의하자.
   
     증가하는 수가 while문 내에서 계속 증가하는게 아닌 조건 하나가 성립하지 않고, 다른 하나는 성립할 때 증가하도록 설정했기에 머릿속에 이를 직관적으로 그리지 못했다. 값을 변화시키는 부분에 유의하고, 이러한 것의 조건은 생각하기 편하도록 최대한 직관적으로 설정해 보자.