5430번 AC

문제링크 : www.acmicpc.net/problem/5430

5430번: AC

---

 

---

<알고리즘>

  1) case 수 T, 명령어 commend, 배열의 수 N, 배열 number를 입력받음

  2) number의 내용을 ,와 ] 기호를 기준으로 숫자와 숫자가 아닌 것을 구분하여 dq에 push_back(두 자리 이상의 수일 경우를 고려하여)

  3) commend의 내용을 앞에서부터 한 자리씩 이행

     3-1) R인 경우 reverse신호를 !reverse로 변경하여 이전과 순서변화가 있음을 표시

     3-2) D인 경우

          3-2-1) dq가 empty면 error 신호 보내고 뒤에서 dq 내용을 출력하지 않도록 errorFlag를 true로 함

          3-2-2) reverse 신호가 true면 pop_back을, false면 pop_front 실행

  4) errorFlag가 false인 경우 reverse 신호를 고려하여 dq를 앞에서부터 혹은 뒤에서부터 출력

 

 

    

 

버전 1. 명령어가 R이면 reverse 함수 사용, D면 empty확인하고 pop_front (시간초과)

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

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int T = 0;
	cin >> T;
	while (T--) {
		string commend = "";
		cin >> commend;
		int N = 0;
		cin >> N;
		
		string number = "";
		cin >> number;
		deque<int> dq;
		for (int i = 0; i < N; i++) {
			dq.push_back(static_cast<int>(number[2 * i + 1]-'0'));
		}

		bool flag = true;
		for (unsigned int i = 0; i < commend.size(); i++) {
			if (commend[i] == 'R') {
				reverse(dq.begin(), dq.end());
			}
			else if (commend[i] == 'D') {
				if (dq.empty()) {
					cout << "error" << "\n";
					flag = false;
					break;
				}
				dq.pop_front();
				--N;
			}
		}

		if (flag) {
			cout << "[";
			for (int i = 0; i < N - 1; i++) {
				cout << dq.front() << ",";
				dq.pop_front();
			}
			cout << dq.front() << "]\n";
		}
	}
	return 0;
}

 

 

 

 

버전 2. reverse 함수 대신 reverse가 있었는지를 boolean 신호로 파악하고 그에따른 다음 행동을 달리하는 방식 ( 메모리 : 3072KB   시간 : 48ms )

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

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int T = 0;
	cin >> T;
	while (T--) {
		//명령어
		string commend = "";
		cin >> commend;

		//배열의 개수
		int N = 0;
		cin >> N;

		//배열의 내용
		string number = "";
		cin >> number;
		
		//입력받은 숫자 deque에 입력
		deque<int> dq;
		if (N != 0) {
			string temp = "";
			for (unsigned int i = 1; i < number.size(); i++) {
				if (number[i] == ',' || number[i] == ']') {
					dq.push_back(stoi(temp));
					temp = "";
				}
				else {
					temp += number[i];
				}
			}
		}
		//명령어에 따른 행동 변화
		bool errorFlag = false;
		bool didReverse = false;
		for (int i = 0; i < commend.size(); i++) {
			if (commend[i] == 'R') didReverse = !didReverse;
			else if (commend[i] == 'D') {
				if (dq.empty()) {
					errorFlag = true;
					cout << "error\n";
					break;
				}
				else {
					//뒤집힌 상태일 경우
					if (didReverse) {
						dq.pop_back();
						--N;
					}
					//뒤집히지 않은 상태일 경우
					else {
						dq.pop_front();
						--N;
					}
				}
			}
		}

		if (!errorFlag) {
			cout << "[";
			if (!dq.empty()) {
				if (didReverse) {
					for (int i = 0; i < N - 1; i++) {
						cout << dq.back() << ",";
						dq.pop_back();
					}
					cout << dq.back();
				}
				else {
					for (int i = 0; i < N - 1; i++) {
						cout << dq.front() << ",";
						dq.pop_front();
					}
					cout << dq.front();
				}
			}
			cout << "]\n";
		}
	}
	return 0;
}