💎 문제
선영이는 주말에 할 일이 없어서 새로운 언어 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만을 넘지 않는다.
ex)
2
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
💎 출력
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.
ex)
[2,1]
error
💎 풀이 방법
정답률이 낮길래 어려울까 했는데 생각보다 수월하게 풀었던 문제였다! 시간초과를 고려하여 어떻게 하면 배열의 뒤에 요소를 제거하고 문자열 입력과 함께 숫자로 변환하는 방법을 생각하는 문제였다!
이 때 deque라는 STL 클래스를 사용하였는데 queue의 일부로 요소의 뒤와 앞 모두 접근할 수 있는 STL클래스이다!! 따라서 이를 이용하여 'R'함수가 오게 되었을 때 뒤의 부분을 삭제할 수 있도록 하여 계속 반복하여 배열의 요소들을 뒤집지 않고서 뒷 요소만 삭제할 수 있게 하였다!!
for(int i = 0;i < testArray.length();i++){
string num = "";
if(testArray[i] != ',' && testArray[i] != '[' && testArray[i] != ']'){
while(testArray[i] != ',' && testArray[i] != '[' && testArray[i] != ']'){
num += testArray[i];
i++;
}
}
if(num != "")
dq.push_back(stoi(num));
}입력받은 배열을 먼저 deque에 집어넣는 과정을 먼저하였다. '[' , ']' , ',' 와 같은 기호들을 제외하고는 입력받은 문자열 안의 숫자들을 꺼내서 deque에 집어넣는 코드를 짰다!! 앞서말한 기호가 아닐 때는 문자열을 숫자로 바꾸는 함수 stoi를 이용하고 이를 deque에 집어넣는 검사를 진행하였다.
for (int i = 0; i < v.size(); i++) {
if(v[i] == 'R'){
if(reverse == true)
reverse = false;
else
reverse = true;
}
else if(v[i] == 'D'){
if(dq.empty())
{
check = false;
break;
}
else{
if(reverse == true)
dq.pop_back();
else
dq.pop_front();
}
}
}뒤이어서는 주어진 함수 p를 실행하도록 하였다. 입력받은 p의 길이 동안 'R'이 입력되었다면 bool 변수를 이용하여 reverse가 되었다는 표시를 해두고 만약 한번 더 입력된다면 다시 false되어 원 상태인 것을 확인할 수 있도록 하였다. 만약 'D'가 입력된다면 deque가 빈상태 인지에 따라서 확인한다! 만약 비어있다면 출력이 error가 될 수 있도록 bool 변수를 이용하고 그 이외의 경우 reverse여부에 따라서 deque에 앞부분 또는 뒷부분의 요소를 삭제해준다!!
if(check == false)
cout << "error" << "\n";
else{
cout << "[";
if(reverse){
for(int i = (dq.size() - 1);i >= 0;i--){
if(i != 0)
cout << dq[i] << ",";
else
cout << dq[i];
}
}
else{
for(int i = 0;i < dq.size();i++){
if(i != dq.size() - 1)
cout << dq[i] << ",";
else
cout << dq[i];
}
}
cout << "]\n";
}다음은 이전 코드를 바탕으로 deque에 있는 내용들을 바꿔주어서 이를 출력하는 과정을 구현하였다! deque에 있던 내용이 이미 비어서 앞서 bool 변수의 내용이 오류를 요한다면 'error'를 출력하도록 하며, 그렇지 않으면 reverse여부에 따라서 삭제한 deque의 내용을 반대로 또는 원래대로 출력해주면 된다!!
💎 전체 코드
#include <iostream>
#include <vector>
#include <deque>
#include <string>
using namespace std;
int T, n;
int main(int argc, const char * argv[]) {
cin >> T;
while(T){
string p;
string testArray;
bool check = true;
bool reverse = false;
cin >> p >> n >> testArray;
deque <int> dq;
vector <char> v(p.length());
for(int i = 0;i < p.length();i++){
v[i] = p[i];
}
for(int i = 0;i < testArray.length();i++){
string num = "";
if(testArray[i] != ',' && testArray[i] != '[' && testArray[i] != ']'){
while(testArray[i] != ',' && testArray[i] != '[' && testArray[i] != ']'){
num += testArray[i];
i++;
}
}
if(num != "")
dq.push_back(stoi(num));
}
for (int i = 0; i < v.size(); i++) {
if(v[i] == 'R'){
if(reverse == true)
reverse = false;
else
reverse = true;
}
else if(v[i] == 'D'){
if(dq.empty())
{
check = false;
break;
}
else{
if(reverse == true)
dq.pop_back();
else
dq.pop_front();
}
}
}
if(check == false)
cout << "error" << "\n";
else{
cout << "[";
if(reverse){
for(int i = (dq.size() - 1);i >= 0;i--){
if(i != 0)
cout << dq[i] << ",";
else
cout << dq[i];
}
}
else{
for(int i = 0;i < dq.size();i++){
if(i != dq.size() - 1)
cout << dq[i] << ",";
else
cout << dq[i];
}
}
cout << "]\n";
}
T--;
}
return 0;
}💎 고민
자료구조의 deque에 대한 내용을 다룬 문제로 쉽게 풀어낼 수 있었다!! 문자열과 합쳐서 나온 문제로 문자열 파싱에 대해서도 고려해볼 수 있어서 좋았던 것 같다. 다음주면 이제 정말 개강이다. 나태해지지말고 알고리즘 문제 꾸준히 풀어서 실력 늘려보자!! 다른 사람들도 잘하고 있지만 나는 그만큼 더 잘할 수 있게 꾸준해보자!! 화이팅하자 규빈
화이팅!!
