[백준 5430번 C/C++] AC

 

[백준 5430번 C/C++] AC

 

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

5430번: AC

---

 

해결전략

 

구현
자료 구조
문자열
파싱
덱

---

 

처음 시도한 코드 - 시간초과

 

#include <iostream>
#include <string>
#include <deque>
using namespace std;

int t;
string p; // 수행할 함수
int n;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> t;
	while(t--)
	{
		cin >> p;
		cin >> n;
		string input;
		cin >> input;
		deque<int> num;
		for(int i=0; i<input.size(); i++){
			if ('0' <= input[i] && input[i] <= '9')
				num.emplace_back(input[i] - '0');
		}

		bool error = false;
		for(int i=0; i<p.size(); i++)
		{
			if(p[i] == 'R'){
				deque<int> temp;
				for(int i = num.size() - 1; i >= 0; i--){
					temp.push_back(num[i]);
				}
				num = temp;
			}
			else if(p[i] == 'D'){
				if (num.size() > 0)
					num.pop_front();
			}

			if (num.size() == 0){
				error = true;
				break;
			}
		}

		if (error == true) cout << "error\n";
		else{
			cout << "[";
			for(int i=0; i<num.size(); i++){
				cout << num[i];
				if (i == num.size() - 1) break;
				cout << ",";
			}
			cout << "]";
		}
	}

	return 0;
}

 

매 번 R 뒤집기를 수행하면 시간초과가 나온다. 

---

 

정답코드

 

#include <iostream>
#include <string>
#include <vector>
#include <deque>
using namespace std;

int t;
string p; // 수행할 함수
int n;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> t;
	while(t--)
	{
		cin >> p;
		cin >> n;
		string input;
		cin >> input;
		deque<int> num;
		int tmp = 0; // 임시 변수, 각 배열 요소를 저장할 변수
		bool blank = true; // 입력 받은 배열 요소가 공백인지 아닌지 판별하는 변수
		for(int i=0; i<input.size(); i++){
			if ('0' <= input[i] && input[i] <= '9'){
				tmp = tmp * 10 + (input[i] - '0');  // 숫자를 읽어들일 때 마다 10을 곱하고 새로운 숫자를 더함
				blank = false; // 배열 요소가 공백이 아님을 표시
			}
			else if (input[i] == ',' || input[i] == ']'){  // ',' 또는 ']'를 만나면 지금까지 읽어들인 숫자를 덱에 삽입
				if (blank == true) continue; // 배열 요소가 공백인 경우 건너뜀
				num.push_back(tmp); // 임시 변수에 저장된 배열 요소를 덱에 삽입
				tmp = 0;  // 임시 변수 초기화
			}
		}
		
		int Rcnt = 0;  // 'R' 함수의 호출 횟수를 저장할 변수
		vector<bool> fOb; // 'R' 함수 호출 시 덱의 앞 또는 뒤에서 요소를 제거할지 저장할 벡터
		bool fb = true; // 덱의 앞에서 요소를 제거할지 뒤에서 요소를 제거할지 판별하는 변수
		for(int i=0; i<p.size(); i++)
		{
			if(p[i] == 'R'){
				Rcnt++;
				fb = fb ? false : true;  // 덱의 앞에서 요소를 제거할지 뒤에서 요소를 제거할지 전환
			}
			else if(p[i] == 'D'){
				if (fb) fOb.push_back(true); // 덱의 앞에서 요소를 제거하면 벡터에 true 삽입
				else fOb.push_back(false); // 덱의 뒤에서 요소를 제거하면 벡터에 false 삽입
			}
		}

		if(Rcnt % 2 == 1) // R 홀수
		{
			deque<int> temp; // 덱의 요소를 뒤집어 저장할 덱
			for (int i = num.size() - 1; i >= 0; i--) {
				temp.push_back(num[i]);
			}

			bool error = false; // 에러가 발생했는지 판별하는 변수
			for (int i = 0; i < fOb.size(); i++)
			{
				if (temp.size() == 0) {
					cout << "error\n";
					error = true; // 에러 발생을 표시
					break;
				}
				if (fOb[i] == true) temp.pop_back();  // 벡터의 요소가 true인 경우 덱의 뒤에서 요소 제거
				else temp.pop_front();  // 벡터의 요소가 false인 경우 덱의 앞에서 요소 제거
			}

			if (error) continue; // 에러가 발생한 경우 다음 테스트 케이스로 넘어감
			else{ // 출력				
				cout << "[";
				for (int i = 0; i < temp.size(); i++) {
					cout << temp[i];
					if (i == temp.size() - 1) break;
					cout << ",";
				}
				cout << "]\n";				
			}			
		}
		else // R 짝수
		{
			bool error = false; // 에러가 발생했는지 판별하는 변수
			for (int i = 0; i < fOb.size(); i++)
			{
				if (num.size() == 0) {
					cout << "error\n";
					error = true; // 에러 발생을 표시
					break;
				}

				if (fOb[i] == true) num.pop_front(); // 벡터의 요소가 true인 경우 덱의 앞에서 요소 제거
				else num.pop_back(); // 벡터의 요소가 false인 경우 덱의 뒤에서 요소 제거
			}

			if (error) continue; // 에러가 발생한 경우 다음 테스트 케이스로 넘어감
			else { // 출력
				cout << "[";
				for (int i = 0; i < num.size(); i++) {
					cout << num[i];
					if (i == num.size() - 1) break;
					cout << ",";
				}
				cout << "]\n";
			}		
		}		
	}

	return 0;
}

 

 

 

 

---