문제 출처

1. 문제설명


  • 두 가지 연산이 있다.
    • R : 배열에 있는 수의 순서를 뒤집는 함수
    • D : 배열의 첫 번째 수를 버리는 함수
  • 배열의 초기값과 수행할 함수가 주어졌을 때 최종 결과를 구하라.
    • 단, 원소가 없는데 D를 사용하는 경우 error를 출력하라



2. 알고리즘 설계


  • 처음 시도는 R 기능을 reverse로 구현하였다.
    • 이건 시간 초과다.
  • 따라서 R이 사용되면, 배열의 뒤부터 값을 제거/출력하고,
  • 다시 R이 사용되면, 배열의 앞부터 값을 제거/출력한다.



3. 로직


  • 가장 적절한 자료구조는 deque이다.
    • 앞, 뒤로 삽입/삭제가 가능한 자료구조이다.
  • 특정 부울 변수를 둬서 R이 사용되면 부울 변수를 역으로 취한다.
    • 부울 변수에 맞춰 뒤에서 삭제할지 결정한다.
  • 이렇게 하면 reverse를 커버칠 수 있다.



4. 전체 코드


#include<bits/stdc++.h>
using namespace std;

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

	int TC; cin >> TC;
	while (TC--) {
		string cmd, num;
		int n;
		cin >> cmd >> n >> num;

		deque<int> dq;
		string tmp = "";
		for (int i = 1; i < num.size() - 1; i++) {
			if (num[i] == ',') {
				dq.push_back(stoi(tmp));
				tmp = "";
			}
			else tmp += num[i];
		}

		if (tmp != "") dq.push_back(stoi(tmp));

		bool chk = false, error = false;
		for (int i = 0; i < cmd.size(); i++) {
			if (cmd[i] == 'R') chk = !chk;
			else if (!dq.empty()) {
				if (chk) dq.pop_back();
				else dq.pop_front();
			}
			else {
				if (!dq.empty()) {
					if (chk) dq.pop_back();
					else dq.pop_front();
				}
				else {
					error = true;
					break;
				}
			}
		}

		if (error) cout << "error\n";
		else {
			cout << '[';
			while (dq.size() > 1) {
				if (chk) {
					cout << dq.back() << ',';
					dq.pop_back();
				}
				else {
					cout << dq.front() << ',';
					dq.pop_front();
				}
			}
			if (!dq.empty()) {
				if (chk) cout << dq.back();
				else cout << dq.front();
			}
			cout << "]\n";
		}
	}

	return 0;
}



5. 소감


  • 문자열 처리가 극악인 문제였다.
    • 입력이 [1,2,3,4] 형태로 들어온다.
    • 출력은 [1,2,3,4]의 형태이다.
  • 비어있는 배열에 뒤집는 연산은 상관없지만, 제거하는 것만 문제가 된다.
  • chk = !chk;
    • 다른 사람 코드를 보면, if-else로 처리한 경우가 많았다.
    • 저렇게 하면 true일 땐, false가 되어 깔끔하게 처리가 가능하다.