백준 / 바킹독님의 문제집 / AC(5430)

문제 설명

 

 

문제 해결

 

처음에 문제 설명 그대로 입력을 받아서 함수조합 문자열을 받고

일일히 함수를 실행하는 코드를 작성했다.

채점한 결과, 시간 초과가 빈번히 발생했다.

 

 

실행 시간을 줄일 수 있는 방법이 없을까 고민해봤다.

반드시 배열을 뒤집은 결과를 일일히 적용시켜야할까?

배열이 뒤집힌 상태 여부만 기억해두고, 맨 앞, 맨 뒤에 있는 원소만 빼줘도 되는 것은 아닐까?

이런 생각이 들었다.

 

#include <iostream>
#include <deque>
#include <string>

using namespace std;

int main(int argc, char* argv[])
{
	// T 입력
	int T;
	cin >> T;

	// AC 프로그램 실행
	while (T--)
	{
		// p 입력
		string p;
		cin >> p;

		// n 입력
		int n;
		cin >> n;

		// 배열 x를 표현한 문자열 입력
		string x_string;
		cin >> x_string;

		// 배열 x 정보 초기화
		deque<int> x;
		if (n != 0)
		{
			int i = 1;
			while (x_string[i] != '\0')
			{
				int z = 0;
				while (x_string[i] >= '0' && x_string[i] <= '9')
				{
					z *= 10;
					z += int(x_string[i] - '0');
					i++;
				}
				if (z != 0)
				{
					x.push_back(z);
				}
				i++;
			}
		}


		// 실제로 일일히 명령어를 수행하면 시간 초과가 난다.
		// 뒤집었다는 사실만 기억하면 된다.
		bool reverse_flag = false;
		bool error_flag = false;

		// 함수 수행
		for (auto cmd = p.begin(); cmd != p.end(); cmd++)
		{
			if (*cmd == 'D')
			{
				if (!x.empty())
				{
					if (reverse_flag)
						x.pop_back();
					else
						x.pop_front();
				}
				else
				{
					error_flag = true;
					break;
				}
			}
			else
				reverse_flag = !reverse_flag;
		}

		// 실행 결과 출력
		if (error_flag)
			cout << "error" << '\n';
		else
		{
			cout << '[';
			if (reverse_flag)
			{
				for (auto i = x.rbegin(); i != x.rend(); i++)
				{
					cout << *i;
					if ((++i)-- != x.rend())
						cout << ',';
				}
			}
			else
			{
				for (auto i = x.begin(); i != x.end(); i++)
				{
					cout << *i;
					if ((++i)-- != x.end())
						cout << ',';
				}
			}
			cout << ']' << '\n';
		}

	}

	return 0;
}

 

역시 사람은 머리를 잘 써야하는 것 같다.