백준 5430번 AC C++ 구현해보기

---

```

백준 5430번 AC C++ 구현해보기

```

 

이번 글을 통해 배워갈 내용

1.  백준 5430번 풀이

---

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

5430번: AC

 

백준 5430번 AC는

난이도 골드 등급의 문제로서

 

테스트 케이스만큼

 

명령어,

숫자의 개수

숫자 개수만큼의 원소를 입력받고

 

명령어가 R일 때 원소 세트를 뒤집고

D일 때 제일 앞에 원소를 지워줍니다.

 

예를 들어 하나의 케이스에

RDD

4

[1,2,3,4]

를 입력받으면

 

처음 R 하고 

[4,3,2,1]

D를 해주고

D를 해주면

[2,1] 이 됩니다.

 

이를 출력해주면 됩니다.

 

만약 D를 받았는데

지울 숫자가 없다면

error를 출력해주면 됩니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

이 문제의 경우

 

주의할 점이

 

숫자의 개수가 100,000이고

테스트 케이스의 길이가 100이기 때문에

 

명령어 RD를 연타로 100번만 받아도

계속 뒤집어야 돼서 진짜 원소를 뒤집으면 시간 초과가 됩니다.

 

따라서 원소를 물리적으로 진짜 뒤집는 게 아니고

논리적으로 뒤집는게 저는 이문제의 키 포인트라 생각합니다.

 

 

 

 

 

 

저는 이러한 문제를 deque를 써서 극복했습니다.

 

각 테스트 케이스 별로 

원소와 명령어를 입력을 받고

함수에 넣어줍니다.

int main()
{
	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	std::string inputStr;

	const int32_t testCastSize = kimc::lib::user_input_int32();

	for (int32_t i = 0; i < testCastSize; i++)
	{
		std::getline(std::cin, inputStr);
		std::string instructionStr = inputStr;

		std::deque<int32_t> ElemDeq = kimc::lib::user_input_deque();

		std::cout << kimc::lib::find_ac_result(instructionStr, ElemDeq) << "\n";
	}

 

앞뒤 방향을 나타내는 enum을 만들고

앞 방향이면 앞 수를 지우고

뒷방향이면 뒷수를 지워주면 됩니다.

클래스와 메서드를 써서

함수를 분할해서 작업하고 싶지만

시간 관계상

매우 큰 함수가 나왔네요 ㅎㅎㅎ

 

명령어를 처리하고

남은 데크를 형식에 맞게 출력만 하면 되는 간단한 함수입니다.

 

	std::string find_ac_result(const std::string instructions, std::deque<int32_t>& ElemDeq) {

		enum Direction
		{
			FRONTFIRST,
			BACKFIRST
		};

		int32_t deqDirection = Direction::FRONTFIRST;
		bool hasError = false;

		for (char ch : instructions)
		{
			if (ch == 'R')
			{
				if (deqDirection == Direction::FRONTFIRST)
				{
					deqDirection = Direction::BACKFIRST;
				}
				else
				{
					deqDirection = Direction::FRONTFIRST;
				}
			}
			else if (ch == 'D')
			{
				if (ElemDeq.empty() == true)
				{
					hasError = true;
					break;
				}
				else
				{
					if (deqDirection == Direction::FRONTFIRST)
					{
						ElemDeq.pop_front();
					}
					else
					{
						ElemDeq.pop_back();
					}
				}
			}
			else
			{
				std::cout << "원치 않는 문자";
			}
		}



		std::string retString = "";
		if (hasError == true)
		{
			retString += "error";
		}
		else
		{
			retString += "[";

			if (deqDirection == Direction::FRONTFIRST)
			{
				while (ElemDeq.empty() == false)
				{
					retString += (std::to_string(ElemDeq.front()) + ",");
					ElemDeq.pop_front();
				}
			}
			else
			{
				while (ElemDeq.empty() == false)
				{
					retString += (std::to_string(ElemDeq.back()) + ",");
					ElemDeq.pop_back();
				}
			}

			if (retString.back() == ',')
			{
				retString.pop_back();
			}
			retString += "]";
		}

		return retString;
	}

}

 

전체 코드는 다음과 같습니다

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <array>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <regex>

namespace kimc::lib {

	int32_t user_input_int32()
	{
		std::string inputStr;
		std::getline(std::cin, inputStr);
		std::stringstream ss(inputStr);

		int32_t retVal = 0;
		if (inputStr != "")
		{
			ss >> retVal;
		}
		return retVal;
	}

	/* 예시 [1,2,3,4] */
	std::deque<int32_t> user_input_deque()
	{
		std::string inputStr;
		std::getline(std::cin, inputStr);
		inputStr = std::regex_replace(inputStr, std::regex(","), " ");
		inputStr = inputStr.substr(1, inputStr.size() - 2);

		std::stringstream ss(inputStr);

		std::deque<int32_t> ElemDeq;

		int32_t tempVal = 0;
		while (ss >> tempVal)
		{
			ElemDeq.push_back(tempVal);
		}
		return ElemDeq;
	}


	std::string find_ac_result(const std::string instructions, std::deque<int32_t>& ElemDeq) {

		enum Direction
		{
			FRONTFIRST,
			BACKFIRST
		};

		int32_t deqDirection = Direction::FRONTFIRST;
		bool hasError = false;

		for (char ch : instructions)
		{
			if (ch == 'R')
			{
				if (deqDirection == Direction::FRONTFIRST)
				{
					deqDirection = Direction::BACKFIRST;
				}
				else
				{
					deqDirection = Direction::FRONTFIRST;
				}
			}
			else if (ch == 'D')
			{
				if (ElemDeq.empty() == true)
				{
					hasError = true;
					break;
				}
				else
				{
					if (deqDirection == Direction::FRONTFIRST)
					{
						ElemDeq.pop_front();
					}
					else
					{
						ElemDeq.pop_back();
					}
				}
			}
			else
			{
				std::cout << "원치 않는 문자";
			}
		}



		std::string retString = "";
		if (hasError == true)
		{
			retString += "error";
		}
		else
		{
			retString += "[";

			if (deqDirection == Direction::FRONTFIRST)
			{
				while (ElemDeq.empty() == false)
				{
					retString += (std::to_string(ElemDeq.front()) + ",");
					ElemDeq.pop_front();
				}
			}
			else
			{
				while (ElemDeq.empty() == false)
				{
					retString += (std::to_string(ElemDeq.back()) + ",");
					ElemDeq.pop_back();
				}
			}

			if (retString.back() == ',')
			{
				retString.pop_back();
			}
			retString += "]";
		}

		return retString;
	}

}


int main()
{
	// 입력 최적화
	std::cin.tie(NULL);
	std::ios::sync_with_stdio(false);

	std::string inputStr;

	const int32_t testCastSize = kimc::lib::user_input_int32();

	for (int32_t i = 0; i < testCastSize; i++)
	{
		std::getline(std::cin, inputStr);
		std::string instructionStr = inputStr;


		std::deque<int32_t> ElemDeq = kimc::lib::user_input_deque();

		std::cout << kimc::lib::find_ac_result(instructionStr, ElemDeq) << "\n";
	}
}

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

참조 및 인용

C++ Primer

Introduction to Algorithms

---

https://codemasterkimc.tistory.com/35

C++ 이론을 배울수 있는 곳 정리

 

https://codemasterkimc.tistory.com/50

300년차 개발자의 좋은 코드 5계명 (Clean Code)

 

---