[백준] 5430번 AC C++ 풀이

---

알고리즘 분류

• 구현
• 알고리즘
• 문자열
• 파싱
• 덱

---

문제 설명

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

---

입력 설명

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

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

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

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

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

---

출력 설명

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

---

예제 입력

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

---

예제 출력

[2,1]
error
[1,2,3,5,8]
error

---

아이디어

입력받은 숫자를 list에 넣고

R이 들어오기 전에는 D가 들어오면 pop_front()하다가

R이 들어오고 D가 들어오면 pop_back()하다가

다시 R이 들어오면 원상복구한다.

이후 최종적으로 list에 남아있는 원소들을 출력해 준다.

---

알고리즘

입력받은 숫자를 list에 넣고

R이 들어오기 전에는 D가 들어오면 pop_front()하다가

R이 들어오고 D가 들어오면 pop_back()하다가

다시 R이 들어오면 원상 복구한다.

이후 최종적으로 list에 남아있는 원소들을 출력해 준다.

비어있는 배열에서 D를 입력하면 에러이다.

---

코드

#include <iostream>
#include <string>
#include <algorithm>
#include <list>
using namespace std;
list<int> init(string);
bool cmd(list<int>&, string, char&);
void pt(list<int>&, char);

int main()
{
	int T; cin>>T;
	while(T--)
	{
		string p,arr;
		int n;
		char cur='F';
		cin>>p>>n>>arr;
		if(n > 0)
		{
			list<int> li = init(arr);
			if(cmd(li, p, cur) == false) pt(li,cur);
		}
		else
		{
			bool isD = false;
			for(int i=0; i<p.size(); i++)
				if(p[i] == 'D') isD = true;
			if(isD) cout<<"error\n";
			else cout<<"[]\n";
		}
	}
	return 0;
}

list<int> init(string arr)
{
	list<int> li;
	string temp="";
	for(int i=1; i<arr.size(); i++)
	{
		if(arr[i]==',' || arr[i] == ']')
		{
			li.push_back(stoi(temp));
			temp = "";
		}
		else temp += arr[i];
	}
	return li;
}

bool cmd(list<int> &li, string p, char &cur)
{
	for(int i=0; i<p.size(); i++)
	{
		if(li.empty())
		{
			cout<<"error\n";
			return true;
		}
		if(p[i] == 'R')
		{
			if(cur == 'R') cur = 'F';
			else if(cur == 'F') cur = 'R';
		}
		else if(p[i] == 'D')
		{
			if(cur == 'R') li.pop_back();
			else if(cur == 'F') li.pop_front();
		}
	}
	return false;
}

void pt(list<int> &li, char cur)
{
	if(li.empty()) {
		cout<<"[]\n";
		return;
	}
	list<string> ans;
	ans.push_back("[");
	if(cur == 'R') reverse(li.begin(), li.end());
	for(auto &a : li)
	{
		ans.push_back(to_string(a));
		ans.push_back(",");
	}
	ans.pop_back();
	ans.push_back("]\n");
	for(auto &a : ans)
		cout<<a;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/5430

R

0

[]

인 경우는 에러가 아니다.

 

RD

0

[]

는 에러이다.

 

R이 들어올 때마다 reverse(li.begin(), li.end()); 를 한다면 시간 초과가 난다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!