백준 5430 cpp // string find,+=시간복잡도, split 구현방법, 예외처리방법

https://www.acmicpc.net/problem/5430]

5430번: AC

*예외처리방법

최악입력 : [] 일때

별도로 처리해준다.

 

*string find,+=시간복잡도

find : O(n)

for(i=0~n)  s+='A' //O(n)

for(i=0~n) s=s+'A' //O(n^2)

결론 : += 를 사용해라.

 

* 의사코드

1.배열을 파싱해서 데큐에 담기

2.명령어를 하나씩돌면서

R이면 참조위치를 앞<->뒤 바궈주기

D이면 참조위치에 맞춰서 pop하기

3. 결과값완성하기

참조위치가 앞이면 d의 원소 앞부터 추가

참조위치가 뒤면 back부터추가, pop

 

* 문제점 : 

substr : O(n) //앞의 []자르기

split : O(n) // ,기준 split하기

파싱된 숫자들을 덱에담기 : O(n)

총 30만 -> 시간초과 가능성

 

//O(n) 최악 : 10만
arr = arr.substr(1, arr.size()-2);
//cout << "arr: " << arr << "\n";

//최악 : O(n) : 10만
vector<string> nums;
nums = split(arr, ",");

//최악 : O(n) : 10만
for (auto s : nums) {
    d.push_back(s);
}

 

* 해결 : 

1. 참조연산자 사용 => 일일히복사 == {대입 O(n)}X , 그대로사용

2.substr대신 idx조정

3.split 대신 쉼표가나오면 push , 덱에바로담기

총 O(n) 만에 해결

기존 : O(3n)

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);
}

 

*내 코드

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

int t,n;
deque<int> d;

void printD(deque<string> d){
	for (auto i : d) {
		cout << i << " ";
	}
	cout << "\n";

}
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);
}
//split : O(n)
vector<string> split(string& input, string deli) {
	long long pos = 0;
	string token = "";
	vector<string> ret;

	//1. 구분자가 있는 위치찾기
	while ((pos = input.find(deli)) != string::npos) {
		//1-1. 문자열자르기, 넣기, 자른문자열 지우기
		token = input.substr(0, pos);
		ret.push_back(token);
		input.erase(0, pos + deli.length());
	}

	//마지막 남은 문자열 넣기
	ret.push_back(input);
	return ret;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> t;
	while (t--) {
		d.clear();
		bool is_front = true;
		string ret="", arr = "";
		string p = "";
		cin >> p;
		cin >> n;
		cin >> arr;

		//예외처리
		//입력이 []이고, D명령이 있는경우 -> error
		//입력이 []이고, D명령이 없는경우 ->[]
		if (arr == "[]") {
			if (p.find("D") != string::npos) {
				cout << "error\n";
				continue;
			}
			else {
				cout << "[]\n";
				continue;
			}
			
		};

		//O(n) 최악 : 10만
		//arr = arr.substr(1, arr.size()-2);
		//cout << "arr: " << arr << "\n";

		//최악 : O(n) : 10만
		//vector<string> nums;
		//nums = split(arr, ",");

		//최악 : O(n) : 10만
		/*for (auto s : nums) {
			d.push_back(s);
		}*/
		
		//해결 : O(n):10만
		parse(arr, d);

		bool is_empty = false;
		int size_p = p.size();
		//최악 : O(n) : 10만 
		for (int i = 0; i < size_p; ++i) {
			if (p[i] == 'R') {
				is_front = !is_front;
			}
			else if (p[i] == 'D') {//"버리는" 함수
				/*cout << "데큐 : ";
				printD(d);
				cout << " size:" << d.size();*/
				if (d.empty()) {
					cout << "error\n";
					is_empty = true;
					break;
				}
				else {
					if (is_front) {
						d.pop_front();
					}
					else {
						d.pop_back();
					}
				}
			}
		}
		if (is_empty) continue;
		//if (d.empty()) continue;
		
		if (is_front) {
			//최악 : O(n) : 10만
			for (auto s : d) {
				ret += to_string(s);
				ret += ",";
			}
			ret = ret.substr(0, ret.size() - 1);
			ret = "[" + ret;
			ret += "]";
		}
		else {
			while (d.size()) {
				ret += to_string(d.back());
				d.pop_back();
				ret += ",";
			}
			ret = ret.substr(0, ret.size() - 1);
			ret = "[" + ret;
			ret += "]";
		}
		cout << ret << "\n";
	}

}

 

*바킹독 코드

rev가 is_front와 유사한역할을한다.

parse를 사용하면, []일때 d.push를 안함 -> 별도예외처리 안해줘도 되는듯 하다.

뒤집을때, 일일히 pop하는 대신 reverse를 사용.

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/e93d3fd7a3bc43179af06505c3f524b0
#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);
    }
  }
}