[C/C++] 백준 5430번

문제출처: https://www.acmicpc.net/problem/5430

[ 문제 ]

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

 

[ 입력 ]

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

 

[ 출력 ]

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

 

[ 풀이 ]

얼핏 보기에는 Deque을 활용하여 "R"이 입력될 때마다 뒤집기를 실행하고, "D"가 입력될 때마다 버리기를 실행하면 해결할 수 있는 간단한 문제이구나! 라고 생각할 수 있다.

하지만, 전체 테스트 케이스의 개수 T의 최댓값이 100, p와 n의 최댓값이 100,000이기에 각 R, D가 입력될 때마다 뒤집기와 버리기를 실행하면 "시간 초과"가 발생한다.

 

시간 초과를 방지하기 위해 크게 세 가지 케이스를 두고 문제를 해결했다.

 

(1) p에 포함된  D(버리기)의 수   >   배열에 들어있는 수의 개수 n  이라면 "error" 출력 후 다음 테스트 케이스 진행

 

(2) p에 포함된 R(뒤집기)의 개수가 0, 2, 4, 6... 짝수라면 bool R = false;  즉, 정방향으로 Deque을 읽는다.

       R == false 일 때 D가 입력되면 Deque은 뒤집히지 않은 상태이므로 pop_front()를 한다.

 

(3) p에 포함된 R(뒤집기)의 개수가 1, 3, 5, 7... 홀수라면 bool R = true;  즉, 역방향으로 Deque을 읽는다.

       R == true 일 때 D가 입력되면 Deque은 뒤집힌 상태이므로 pop_back()를 한다.

 

p의 값을 전부 읽어 R의 상태를 구한 후 R == false 이면 정방향으로, R == true 이면 역방향으로 Deque을 읽는다.

 

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

using namespace std;

int count_D(string& p)
{
	int n = 0;
	for ( int i = 0; i < p.length(); i++ )
	{
		if ( p[i] == 'D')
		{
			n++;
		}
	}
	return n;
}

int main(void)
{
	int T, n_D, n;
	cin >> T;
	
	for ( int i = 0; i < T; i++ )
	{
		string p, x;
		cin >> p;
		n_D = count_D(p);
		deque<int> dq;
		
		cin >> n;
		
		string s = "";
		cin >> x;
		for ( int j = 0 ; j < x.length() ; j++ )
		{
			if ( isdigit(x[j]) )
			{
				s += x[j];
			}
			else
			{
				if ( !s.empty() )
				{
					dq.push_back(stoi(s));
					s = "";
				} 
			}
		}
		
		if ( n_D > n )
		{
			cout << "error" << endl;
			while ( !dq.empty() )
			{
				dq.pop_front();
			}
			continue;
		}
		
		bool R = false;
		
		for ( int z = 0 ; z < p.length(); z++ )
		{
			if ( p[z] == 'R' )
			{
				R = !R;
			}
			else if ( p[z] == 'D' )
			{
				if ( R )
				{
					dq.pop_back();
				}
				else
				{
					dq.pop_front();
				}
			}
		}
		
		cout << "[";
		if ( !R && !dq.empty() )
		{
			for ( deque<int>::iterator it = dq.begin(); it != dq.end(); it++ )
			{
				if ( it == dq.end()-1 )
				{
					cout << *it;
				}
				else
				{
					cout << *it << ",";
				}
			}
		}
		else if ( R && !dq.empty() )
		{
			for (deque<int>::reverse_iterator it=dq.rbegin();it!=dq.rend(); it++)
			{
				if ( it == dq.rend()-1 )
				{
					cout << *it;
				}
				else
				{
					cout << *it << ",";
				}
			}
		}
		cout << "]" << endl;
		
	}
	
	return 0;
}

+ 추가) Deque이 필요한 이유는 R의 상태에 따라 pop_back() or pop_front() 해야하기 때문

+ 추가) 연결리스트로 Deque을 구현하여 해결할 수도 있을 것이다.