[5430] AC - 구현/문자열/덱 ★★☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/5430

5430번: AC

---

[ 문제 접근 ]

 

문제 이름 답게 풀다 보면 에이씨.. 가 절로 나오는 그런 문제다.

 

 처음 문제를 읽고

 

① 입력으로 주어진 [1,2,3,4] 을 1 2 3 4 로 split 하는 부분.

② reverse 하는 부분.

 

이 관건이겠구나.  싶었다.

 

아래는 내 긴 여정이 담긴 최종 코드다. 

어디서 해맸는지 자세하게 기록해보자.

 

그래도 이 문제 풀고 얻어 간게 몇 가지 있었다 ;)

---

[ 최종 코드 ]

 

#include<iostream>
#include<algorithm>
#include<deque>
#include<string>
#include<sstream>
 
using std::cout; using std::cin;
using std::deque; using std::string;
 
int n, t;
string p;
string s_arr;
 
deque<int> split(string input, char delimeter) {
	deque<int> answer;
	
	input.erase(input.begin()); //input.erase(0)      '['  지움
	input.erase(input.end() - 1);             //      ']'  지움
 
 
	std::stringstream ss(input);
	string num = "";
	while (getline(ss, num, delimeter)) {
		answer.push_back(std::stoi(num));
	}
	return answer;
}
 
 
int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
 
	cin >> t;
	while (t--) {
		cin >> p;
		cin >> n;
	
		cin.ignore(10, '\n');
		getline(cin, s_arr);
 
		s_arr.erase(s_arr.begin()); //input.erase(0)  '['  지움
		s_arr.erase(s_arr.end()-1);                  // ']'  지움
 
		deque<int> arr = split(s_arr,',');
 
		bool is_error = false;
		bool reverse = false;
 
		for (size_t i = 0; i < p.length(); i++) {
			if (p[i] =='R') {
				//std::reverse(arr.begin(), arr.end());
				reverse = !reverse;
			}
			else {
				if (arr.empty()) { 
					cout << "error\n";
					is_error = true;
					break;
				}
				if (reverse) {
					arr.pop_back();
				}
				else {
					arr.pop_front();
				}
			}
		}
		// 출력
		if (!is_error) {
			if (arr.empty()) {
				cout << "[]\n";
			}
			else {
				cout << "[";
				if (reverse) {
					for (auto ritr = arr.rbegin(); ritr != arr.rend(); ritr++) {
						if (ritr == arr.rend()-1) {
							cout << *ritr;
							break;
						}
						cout << *ritr << ",";
					}
				}
				else {
					for (int i = 0; i < arr.size(); i++) {
						if (i == arr.size() - 1) {
							cout << arr[i];
							break;
						}
						cout << arr[i] << ",";
					}
				}
				cout << "]\n";
			}
		}
		s_arr.clear();
	}
 
	return 0;
 
}

 

 

 

자기전에 한 문제만 풀고 자려다가 피 봤다..

차라리 저 틀렸습니다 가 더 좋더라 요샌.. 

 

 

---

[ Key Point ]

 

👉 우선 14 ~ 27  split 함수 부터 보자.   

deque<int> split(string input, char delimeter) {
	deque<int> answer;
	
        input.erase(input.begin()); //input.erase(0)      '['  지움
	input.erase(input.end() - 1);                  // ']'  지움
    
	std::stringstream ss(input);
	string num = "";
	while (getline(ss, num, delimeter)) {
		answer.push_back(std::stoi(num));
	}
	return answer;
}

input.erase(input.end() - 1); // ']' 지움

' ] ' 지우려고 처음에는 input.erase(input.end()); 이렇게 썼는데 ] 가 지워지지 않았다.

 

그래서 erase 함수를 급하게 찾아보니 

1. iterator erase (const_iterator position);
2. iterator erase (const_iterator first, const_iterator last);

1 번은 pos 의 값 지우는거고,   2번은 first 부터 last 전까지 지우는거다. 

나는 1번을 사용해야하니 end() 가 아닌 end()-1을 해야 마지막 원소를 지울 수 있다.

 

나머지는 평범한 stringstream을 이용한 평범한 split 함수.

 

---

 

👉 원래는 deque 이 아니라 vector를 이용해서 풀었었다. 그러다가 자꾸 오류 나니깐 괜히 벡터 때문인가 싶어서 벡터를 덱으로 바꾼거다.

( 풀고 보니 벡터를 사용하면 시간 초과가 나온다는 글 들을 여럿 봤다.

벡터 원소 삭제시 한 칸씩 땡겨지는데 이 과정이 reverse 와 마찬가지로 O(N) 의 시간복잡도를 가지기 때문. )

 

 

<algorithm> 에 있는 reverse 함수를 사용했는데 이러면 시간초과 가 뜬다.

//std::reverse(arr.begin(), arr.end());
reverse = !reverse;

그래서 bool 타입 reverse flag 하나 만들어서 reverse가 true 면 원소를 뒤에서 pop 하고 false면 앞에서 pop 하게끔 구현했다.

if (reverse) {
	arr.pop_back();
}
else {
	arr.pop_front();
}

---

 

👉 계속 오류가 나서 다른 사람 블로그를 보다가 이 부분을 보고 풀 수 있었다.

 

---

👉 계속 하는 실수인데 test case 가 여러개 주어질때는 항상 전역변수 초기화하는거 잊지 말자!! 

이것 때문에도 몇번 틀렸다.

 

s_arr.clear();

---

[ 다른 사람 풀이 ]

 

ref :: https://koolreview.tistory.com/65

ref ::