백준 5430 - AC

문제링크

• 백준 5430

문제설명

• 두 가지 함수 R(뒤집기), D(맨 앞 숫자 버리기)가 있다.
• 수행할 함수 p는 R과 D의 조합으로 이루어져 있으며, 숫자가 담긴 배열이 주어졌을 때 함수 p를 실행한 결과를 출력
  • 비어 있을 떄 D 함수를 수행하게 되는 경우 error 를 출력해야 한다.
  • 함수 p를 수행한 이후에 배열이 비어 있다면 [] 를 출력한다.

시간초과 해결 방법

• 처음에는 주어진 함수 p에 대해서 R, D 함수를 모두 수행하게 했다. 즉, 함수 p에 RRRRRR 와 같이 순서를 뒤집는 의미가 없는 경우에도 뒤집는 로직을 실행하면서 시간초과에 걸렸다.
  • 더불어, 뒤집는 로직도 새로운 배열에 모두 push_back() 을 수행하는 방법으로 구현했는데, p의 길이가 최대 60만인 것을 고려했을 때 결코 적은 시간이 아니라고 생각했다.
• 처음 입력받은 함수 p에 대해서 R의 개수가 홀수일때만 한번 실행할 수 있도록 한다.
• 배열이 빈 상태에서 D 함수를 실행하게 되면 error 를 출력하고 해당 케이스는 바로 빠져나올 것
• R 함수의 경우 순방향인지, 역방향인지만 바꿔주도록 하고 덱(deque) 자료구조를 이용하여 pop_front(), pop_back() 메서드를 활용하여 D 함수를 구현

구현

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

int dir; // 0: 정방향, 1: 역방향

int functionD(deque<int>& dq) {
	if (dq.size() == 0) return -1;

	if (dir == 0) dq.pop_front();
	else dq.pop_back();

	return 1;
}

void command(string p, deque<int>& dq) {
	for (int i = 0; i < p.size(); i++) {
		if (p[i] == 'R') {
			dir = ~dir; // not 연산
		}
		else if (p[i] == 'D') {
			if (functionD(dq) == -1) {
				printf("error\n");
				return;
			}
		}
	}

	printf("[");
	if (dir == 0) {
		for (int i = 0; i < dq.size(); i++) {
			if (i == dq.size() - 1) printf("%d", dq[i]);
			else printf("%d,", dq[i]);
		}
	}
	else {
		for (int i = dq.size() - 1; i >= 0; i--) {
			if (i == 0) printf("%d", dq[i]);
			else printf("%d,", dq[i]);
		}
	}
	printf("]\n");
}

string getRealP(string p) {
	string ret;
	int cnt = 0;
	for (int i = 0; i < p.length(); i++) {
		if (p[i] == 'R') {
			cnt++;
		}
		else if (p[i] == 'D') {
			if (cnt == 0) {
				ret.push_back(p[i]);
				continue;
			}
			if (cnt % 2 == 1) ret.push_back('R');
			ret.push_back(p[i]);
			cnt = 0;
		}
	}
	if (cnt > 0 && cnt % 2 == 1) 
		ret.push_back('R');

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int T;
	cin >> T;
	for (int testCase = 0; testCase < T; testCase++) {
		dir = 0;
		string p;
		cin >> p;
		p = getRealP(p);
		int n; 
		cin >> n; getchar();
		string origin, numArr;
		cin >> origin;
		for (int i = 0; i < origin.size(); i++) {
			if (origin[i] == '[' || origin[i] == ']') continue;
			numArr.push_back(origin[i]);
		}
		deque<int> dq;
		stringstream ss(numArr);
		string token;
		int num;
		while (getline(ss,token, ',')) {
			num = stoi(token);
			dq.push_back(num);
		}
		command(p, dq);
	}
	return 0;
}