[C++]백준 5430번: AC

문제

 

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

5430번: AC

 

문제이해

 

• 테스트 케이스의 개수가 입력으로 주어진다.
• 테스트 케이스만큼 수행할 함수와 배열에 들어있는 수의 개수, 배열이 입력된다.
• 함수가 수행된 결과를 출력한다. 만약 에러가 발생하는 경우에는 error를 출력한다.

 

명령어에는 R과 D가 있다. R은 전체 배열의 순서를 뒤바꾸는 것이고 D는 배열의 첫 번째 원소를 제거하는 것이다.

 

우선 R부터 봤을 때 전체 배열의 순서를 뒤바꾸는 함수인 reverse는 시간복잡도가 O(n)으로 R이 나올 때마다 reverse를 하게 되면 반드시 시간 초과가 될 수밖에 없다. 이 문제를 해결하기 위해선 그냥 배열이 정방향인지 역방향인지 정해놓은 후 정방향이면 그대로 출력하고 역방향이면 배열의 뒤에서부터 출력하기만 하면 된다.

 

R을 직접 reverse하지 않기로 했기 때문에 D가 어쩔 땐 배열의 첫 번째 원소를 삭제할 수도 있고 또 어쩔 땐 배열의 마지막 원소를 삭제할 수도 있다.

배열의 첫번째 원소와 마지막 원소를 원활하게 빼기 위해선 deque를 이용하면 된다. 

 

문제해결

 

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <queue>
using namespace std;

void vk(string nums, deque<int>& result) {
	nums.erase(nums.begin(), nums.begin() + 1);
	nums.erase(nums.end() - 1, nums.end());

	deque<int> numbers;
	stringstream S(nums);
	string token;

	while (getline(S, token, ',')) {
		int number = stoi(token);
		numbers.push_back(number);
	}
	result = numbers;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T, N;
	cin >> T;
	string str;
	string numbers;
	for (int i{ 1 }; i <= T; i++) {
		int check = 0;
		cin >> str >> N >> numbers;
		deque<int> test;
		int way = 1;
		vk(numbers, test);
		for (int i{ 0 }; i < str.size(); i++) {
			if (str[i] == 'D') {
				if (way == 1) {
					if (test.size() == 0) {
						check = 1;
						break;
					}
					else {
						test.pop_front();
					}
				}
				else {
					if (test.size() == 0) {
						check = 1;
						break;
					}
					else {
						test.pop_back();
					}
				}
			}
			else {
				way *= -1;
			}
		}
		if (check == 1) {
			cout << "error\n";
		}
		else {
			if (way == 1) {
				cout << "[";
				for (int i{ 0 }; i < test.size(); i++) {
					if (i == test.size() - 1) {
						cout << test[i];
					}
					else {
						cout << test[i] << ",";
					}
				}
				cout << "]\n";
			}
			else if (way == -1) {
				cout << "[";
				for (int i = test.size() - 1; i >= 0; i--) {
					if (i == 0) {
						cout << test[i];
					}
					else {
						cout << test[i] << ",";
					}
				}
				cout << "]\n";
			}
		}
	}
}

 

void vk

해당 문제에서는 배열을 숫자만 받는 것이 아닌 "["와 "]"와 ", "가 추가로 나오기 때문에 배열을 string으로 받고 거기서 숫자만 뽑아내 deque <in>에 저장하도록 하기 위해 사용된 함수이다.

 

int main

정방향의 경우 way = 1 역방향의 경우 way = -1로 설정하였고 way가 1인 경우엔 pop_front(); -1인 경우에는 pop_back();을 해주면 된다. 이후 way의 값에 따라 출력 방향만 설정해 주면 된다.

 

문제후기

시간을 줄이기 위해 어떻게 해야되는지 고민이 많이 필요했던 문제 같다.