[백준] 알고리즘 C++ 5430번 - AC문제

문제

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

5430번: AC

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <stdio.h>
#include <stack>
#include <string>
#include <deque>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int T;
	cin >> T;
	while (T--) {
		deque<int> dq;
		int n;
		string p;
		cin >> p >> n;
		string arr;
		cin >> arr;
		string temp = "";
		bool flag = true;
		bool reverse_dq = false;
		bool first_error = true;
		if (n == 0) {
			for (int i = 0; i < p.size(); i++) {
				if (p[i] == 'D') {
					cout << "error" << "\n";
					first_error = false;
					break;
				}
			}
			if (first_error)
				cout << "[]" << "\n";
			continue;
		}
		for (int i = 0; i < arr.size(); i++) {
			if (i == arr.size() - 1) {
				dq.push_back(stoi(temp));
			}
			else if (arr[i] == ',') {
				dq.push_back(stoi(temp));
				temp = "";
			}
			else if (arr[i] == '[' || arr[i] == ']') continue;
			else temp += arr[i];
		}

		for (int i = 0; i < p.size(); i++) {
			if (p[i] == 'R') {
				if (reverse_dq) {
					reverse_dq = false;
				}
				else
					reverse_dq = true;
			}
			else {
				if (dq.empty()) {
					cout << "error" << "\n";
					flag = false;
					break;
				}
				else {
					if (reverse_dq) {
						dq.pop_back();
					}
					else dq.pop_front();
				}
			}
		}
		if (flag) {
			cout << "[";
			while (!dq.empty()) {
				if (reverse_dq) {
					cout << dq.back();
					dq.pop_back();
				}
				else {
					cout << dq.front();
					dq.pop_front();
				}
				if (!dq.empty())
					cout << ",";
			}
			cout << "]" << "\n";
		}

	}
}

해설

소스코드가 조금 지저분하다.

이 문제는 단순하게 보면 쉬워보인다. R명령어 일때는 배열을 반대로 D 명령어 일때는 맨앞의 요소를 삭제 큐를 쓰던가 덱을 쓰면 될 것 같다.

 

이 문제는 덱을 사용하면 편한 이유가 따로 있다.

큐를 이용해 REVERSE 알고리즘을 사용하게 되면 대부분 시간초과로 인해 문제를 해결 할 수 없다.

이 문제는 덱을 이용해서 앞에서 뺄 건지 뒤에서 뺄 건지를 결정해야 하는 문제이다.

 

먼저 문자열 부분은 여러가지 방식이 있으니 참고만 하자.

이후 R의 명령어를 구분하기 위해 reverse_dq 라는 bool 형식을 선언하였다.

이 말은 무엇인가 하면 R이 한번 왔을 때 true로 해줌으로써 뒤에 있는 요소를 빼주고 또다시 R이 왔을 경우는 false로 해줌으로 써 앞에 있는걸 뺄 수 있게 해준다.

 

대충 소스코드 보시면 이해하실겁니다.

 

문제는 50%에서 틀렸습니다. 라고 뜨는 경우가 있습니다.

시간초과 부분은 reverse 말고 한번 연산하는걸로 해주면 해결됩니다.

문제는 50%틀린 부분은

 

입력부분을 생각해보시면 n=0일때 처음에 전부다 error 처리를 했지만

1

R 0 [] 의 입력의 예상 값은 []로 출력되어야 합니다.

 

이부분 생각해보시고 작성하시면 맞게 될 것 입니다.