C++ 백준 5430 AC

백준 5430

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

5430번: AC

 

풀이 전 나의 생각

정수 배열 연산 AC는 R(뒤집기)과 D(버리기)가 있다.
이때, 주어진 배열에 AC 연산을 연산을 적용하여 나오는 결과값을 구해야 한다. 

 

조건

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

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

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

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

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

 

과정

조건을 보면 배열의 수가 10만, 수행할 함수가 10만의 범위를 가진다.

시간 제한도 1초기 때문에 O(N^2)의 속도를 가지지 않도록 풀이를 진행해야 한다.

 

풀면서 시간복잡도가 늘어날 것이라고 예상했던 부분은

1. 함수p를 다루는 부분에서 R과 D를 수행하게 되는데
워낙에 p의 범위가 크기 때문에 덱의 리버스를 진행하는 부분에서 
내장 기능의 reverse 메서드를 사용하지 않았다.

2. 마지막에 결과값을 출력할 때, while을 사용하여 큐를 끝까지 뺄 때까지
front, back, pop을 하는 과정을 거치지 않고
덱의 기능 중 rbegin, rend가 있는데 이를 이용하여 리버스를 하는 부분과
안하는 부분을 나눠 for문으로 결과값을 출력했다.

과정은 다음과 같다.
1. 배열의 정보를 덱에 넣는다.
2. 주어진 함수를 실행한다.
3. 리버스인지 아닌지 판단하여 결과를 출력한다.

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>
#include <deque>

using namespace std;

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

	int T, n;

	cin >> T;

	while (T--)
	{
		deque<string>dq;
		string p, x, str = "";
		bool er = false, rev = false;
		cin >> p >> n >> x;

		for (int i = 0; i < x.length(); i++)
		{
			//숫자라면 문자열에 현재 문자를 붙여줌
			if (isdigit(x[i]))
			{
				str += x[i];
			}
			// 숫자가 아닌 문자가 들어 왔다면
			else
			{
				if (!str.empty())
				{
					//이전에 만들어 놓았던 숫자 문자열을 넣어줌
					dq.push_back(str);
					str = "";
				}
			}
		}

		for (int i = 0; i < p.size(); i++)
		{
			//리버스를 R이 나올 때 마다 하는 것이 아닌 리버스 인지 아닌지만 판단
			if (p[i] == 'R')
			{
				if (!rev) rev = true;
				else rev = false;
			}
			else
			{
				//덱이 비어 있는데 접근한다면 에러 출력
				if (dq.empty())
				{
					cout << "error" << "\n";
					er = true;
					break;
				}
				// 리버스일 경우 뒤를 빼주고 아니라면 앞을 빼준다.
				if (rev) dq.pop_back();
				else dq.pop_front();
			}		
		}
		//에러가 아니라면
		if (!er)
		{
			cout << "[";

			//리버스일 경우
			if (rev) 
			{
				for (auto i = dq.rbegin(); i != dq.rend(); i++) {
					if (i == dq.rend() - 1)
						cout << *i;
					else
						cout << *i << ',';
				}
			}
			//아닐 경우
			else 
			{
				for (auto i = dq.begin(); i != dq.end(); i++) {
					if (i == dq.end() - 1)
						cout << *i;
					else
						cout << *i << ',';
				}
			}
			
			cout << "]" << '\n';
		}
	}
}