5430번: AC
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.
www.acmicpc.net
접근 방법
알고리즘 : 덱
테스트 케이스를 출력하는 것까지는 성공했지만, 시간초과 발생.
N이 100,000개일때 예상은 했지만 최적화 시킬 수 있는 방법을 생각하지는 못했다.
reverse 함수를 최대한 요소를 줄이고 진행하는 방법으로 확인.
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
freopen("input.txt", "r", stdin); //제출 시 삭제
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--){
string cmd,arr;
int n;
cin>>cmd;
cin>>n;
cin>>arr;
deque<int>dq;
if(n==0||cmd==""){
cout<<"error"<<"\n";
} else{
for(char a : arr){
if(a =='['||a==']'||a==','){
continue;
} else{
dq.push_back(a-'0');
}
}
for(char a:cmd){
if(a == 'R'){
reverse(dq.begin(),dq.end());
}
if(a == 'D'){
if(!dq.empty()) dq.pop_front();
}
}
if(dq.empty()){
cout<<"error"<<"\n";
} else{
cout<<"[";
for(int i=0;i<dq.size();i++){
if(i == dq.size()-1){
cout<<dq[i];
} else{
cout<<dq[i]<<",";
}
}
cout<<"]"<<"\n";
}
}
}
}
C++ 정답코드
#include <bits/stdc++.h>
using namespace std;
void parse(string& tmp, deque<int>& d){
int cur = 0;
for(int i = 1; i+1 < tmp.size(); i++)
{
if(tmp[i] == ','){
d.push_back(cur);
cur = 0;
}
else{
cur = 10 * cur + (tmp[i] - '0');
}
}
if(cur != 0)
d.push_back(cur);
}
void print_result(deque<int>& d){
cout << '[';
for(int i = 0; i < d.size(); i++)
{
cout << d[i];
if(i+1 != d.size())
cout << ',';
}
cout << "]\n";
}
int t;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while(t--){
deque<int> d;
int rev = 0;
int n;
bool isWrong = false;
string query, tmp;
cin >> query;
cin >> n;
cin >> tmp;
parse(tmp, d);
for(char c : query)
{
if(c == 'R')
rev = 1 - rev;
else{
if(d.empty()){
isWrong = true;
break;
}
if(!rev) d.pop_front();
else d.pop_back();
}
}
if(isWrong)
cout << "error\n";
else{
if(rev) reverse(d.begin(), d.end());
print_result(d);
}
}
}
'코딩테스트(알고리즘) > baekjoon' 카테고리의 다른 글
[baekjoon] 그림 1926 (C++) (0) | 2022.06.17 |
---|---|
[baekjoon] 균형잡힌 세상 4949 (Javascript, c++) (0) | 2022.06.16 |
[baekjoon] 오큰수 17298 (Javascript,c++) (0) | 2022.06.15 |
[baekjoon] 옥상 정원 꾸미기 6198 (Javascript, c++) (0) | 2022.06.15 |
[baekjoon] 탑 2493 (Javascript,c++) (0) | 2022.06.15 |