https://www.acmicpc.net/problem/5430
문제
> 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다.
> AC는 정수 배열에 연산을 하기 위해 만든 언어이다.
> 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.
> 함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다.
> 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.
> 함수는 조합해서 한 번에 사용할 수 있다.
> 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다.
> 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.
> 배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.접근
정수배열이라고 주어진 문자열을 입력받는다. 하지만 필요한건 대괄호와 콤마를 뺀 숫자들이므로 이를 조건문으로 파싱해 숫자만 뽑아내준다.
뽑아낸 숫자(문자열형)로 이루어진 디큐를 가지고 명령어를 처리한다. R에 대해 디큐 안의 원소를 역순정렬하고, D에 대해선 디큐의 front_pop으로 지워준다. 만약 D에 대해 처리하기 전 디큐가 비어있다면 error을 출력하고 다음 케이스로 넘어가도록 해준다.
연산이 끝나면 다시 대괄호 안에 콤마로 숫자를 구분한 정수배열 형태로 만들어 출력한다.
문제해결
> 테스트 케이스의 개수를 입력받고, 명령어 str, 정수배열의 크기 n, 정수 배열 arr을 입력받고 정수 배열 내 숫자를 뽑아 저장할 deque를 선언한다.
> arr을 돌며 '['가 있으면 필요없으므로 건너 뛰고 ,와 ']'를 본다. 둘이 아닌 다른문자(숫자)가 나오면 cnt를 누적하고 이 두 문자중 하나라도 나오면 현 i값에서 cnt를 하나씩 빼며 문자열을 거슬러 어디부터 어디까지가 숫자인지를 골라내 rst에 저장한다.
> 저장하면 다시 cnt를 초기화 시키고 다음 문자를 보며 뽑아낼 숫자를 누적한다.
> 이제 rst에 숫자만 저장이 됐고, valid 부울로는 D연산에서 원소가 없을 때 error을 출력하기 위해 while을 깨주는 역할을 하고 rvs는 디큐를 실제로 뒤집지 않고 뒤집었다 를 표현하기 위한 변수이다.
> R이 명령어로들어오면 rvs값을 반전시켜 역순이다 라고 표시해주고, 아래 D명령어에서 이 rvs값에 따라 front를 pop할지 back을 pop할지 선택한다.
> 명령어 처리가 끝나면 또 rvs값에 따라 참이면 역순으로 정렬하고, 거짓이면 그대로 정렬한다.
> valid값에 따라 error가 아니면 출력형태에 맞춰 출력한다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int T;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> T;
while (T--)
{
string str;
cin >> str;
int n;
cin >> n;
string arr;
cin >> arr;
int cnt = 0;
deque<string> rst;
for (int i = 0; i < arr.size(); i++)
{
if (arr[i] == '[') continue;
if (arr[i] == ',' || arr[i] == ']')
{
if (arr[i] == ']' && arr[i - 1] == '[') continue;
string tmp;
for (int j = cnt; j > 0; j--) tmp += arr[i - j];
rst.push_back(tmp);
cnt = 0;
continue;
}
cnt++;
}
bool valid = true;
bool rvs = false;
for (int i = 0; i < str.size(); i++)
{
if (str[i] == 'R')
{
rvs = !rvs;
}
else
{
if (rst.empty())
{
cout << "error" << '\n';
valid = false;
break;
}
if (rvs)
rst.pop_back();
else
rst.pop_front();
}
}
if (rvs) reverse(rst.begin(), rst.end());
if (valid)
{
cout << "[";
for (int i = 0; i < rst.size(); i++)
{
if (i + 1 == rst.size())
{
cout << rst[i];
}
else
cout << rst[i] << ",";
}
cout << "]" << '\n';
}
}
}
후기
시간초과가 나서 코드를 다시 봤다. 처음엔 rvs로 표시해주지 않고, 디큐도 아닌 벡터로 rst를 받아 그냥 R들어오면 reverse하고, D들어오면 erase로 지웠다. 두 명령어가 정렬을 하는 명령어이므로 시간복잡도가 o(N^2)이 되므로 시간초과가 난다.
