개발/알고리즘

백준 1874번 : 스택 수열

라사 RASA 2023. 2. 13. 17:37

문제 접근


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

 

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

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

 

 

 

문제 코드


#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 알고리즘 레콩키스타 - 시작

목적 : 과거 PS 감각의 회복 목표 : Class 4 금장 획득 기간 : 23년 02월, 한 달 전략 : 한 문제당 최대 1시간씩, 하루 최소 1문제 풀이 (필요하다면 자료 구조 학습과 다른 문제 풀이 병행) 주의점 : 정리

memoria-aeon.tistory.com

 

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

 

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

 

 

  1. 문제를 풀이하며, 조건을 보고, 확실한 기준을 만들자.

      이번에 증가하는 정수, 원하는 수열, 스택 등 어떤 것을 기준으로 삼을지 확실히 정하지 않아 시간이 조금 지체됐다.

  2. 값을 변화시키는 부분의 유의하자.

      증가하는 수가 while문 내에서 계속 증가하는게 아닌 조건 하나가 성립하지 않고, 다른 하나는 성립할 때 증가하도록 설정했기에 머릿속에 이를 직관적으로 그리지 못했다. 값을 변화시키는 부분에 유의하고, 이러한 것의 조건은 생각하기 편하도록 최대한 직관적으로 설정해 보자.