[백준5430] AC (C++)

📌 문제

BOJ 바로가기

문자열의 형태로 배열을 입력받은 후 R(reverse)연산 또는 D(delete) 연산을 진행해준 결과를 출력해야 한다.

🗡 풀이

고려해야 할 점은 두 가지이다.

• 문자열을 입력받고 숫자만을 추출해서 덱에 넣어야 함
• R 연산을 해야 한다고 해서 실제로 배열을 뒤집으면 시간 초과가 뜬다.

📍 숫자만 덱에 push

string temp = "";
for (int i = 1; i < num.length(); i++) {
	if (isdigit(num[i]))
		temp += num[i];
	else {
		if (!temp.empty()) { // []이 입력될 경우를 제외하고 숫자 push
			q.push_back(stoi(temp));
			temp = "";
		}
	}
}

📍 reverse 연산 시 덱을 실제로 뒤집는 대신 boolean형 변수를 선언해서 뒤집어졌는지, 아닌지를 표시해준다.

if (p[i] == 'R')
	reverse = reverse ? false : true;

📍 reverse 되어 있다면 D 연산 시 덱의 pop_back() 연산을 진행해준다. 그렇지 않다면 pop_front()연산을 진행한다.

📍 출력할 때도 reverse 여부를 고려해서 출력해줘야 한다.

🥶 string형으로 입력받은 후 숫자를 추출해야 하는 문제는 처음 봐서 꽤나 고생했다. string 변수에 += 연산이 가능하다는 걸 처음 알게 되었다.

🥶 처음에는 덱을 두 개 선언해서 R 연산이 들어오면 진짜로 뒤집어줬는데, FIFO와 LIFO 모두 가능한 덱에서는 이 방법이 상당히 비효율적이었다. 코드를 짜기 전에 시간복잡도 계산을 선행해줬어야 했다.. 결국 마지막에 코드를 뜯어고쳤다.

🚩 소스코드

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		// 함수, 배열 입력받기
		string p, num;
		int n;
		cin >> p >> n >> num;
		// 숫자만 덱에 push!
		deque<int> q;
		string temp = "";
		for (int i = 1; i < num.length(); i++) {
			if (isdigit(num[i]))
				temp += num[i];
			else {
				if (!temp.empty()) { // []이 입력될 경우를 제외하고 숫자 push
					q.push_back(stoi(temp));
					temp = "";
				}
			}
		}
		// 함수 수행
		bool error = false;
		bool reverse = false;
		for (int i = 0; i < p.length(); i++) {
			// reverse를 true면 false, false면 true로 바꿔줌
			if (p[i] == 'R')
				reverse = reverse ? false : true;
			// 삭제 연산
			else if (!q.empty() && p[i] == 'D') {
				if (reverse)
					q.pop_back();
				else
					q.pop_front();
			}
			// 큐가 비어있는데 삭제연산이 들어옴 (오류)
			else if (q.empty() && p[i] == 'D') {
				error = true;
				break;
			}
		}
		// 결과 출력
		if (error) cout << "error" << '\n';
		else {
			cout << '[';
			while(!q.empty()) {
				// 뒤집혀있으면 뒤에서부터 pop
				if (reverse) {
					cout << q.back();
					q.pop_back();
				}
				// 뒤집혀있지 않으면 앞에서부터 pop
				else {
					cout << q.front();
					q.pop_front();
				}
				if (q.size() != 0)
					cout << ',';
			}
			cout << ']' << '\n';
		}
	}
}

🚩 오답 소스코드 (시간초과)

#include <iostream>
#include <deque>
#include <string>
using namespace std;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t;
	cin >> t;
	while (t--) {
		// 함수, 배열 입력받기
		string p, num;
		int n;
		cin >> p >> n >> num;
		deque<int> q;
		string temp = "";
		for (int i = 1; i < num.length(); i++) {
			if (isdigit(num[i]))
				temp += num[i];
			else {
				if (!temp.empty()) {
					q.push_back(stoi(temp));
					temp = "";
				}
			}
		}
		// 함수 수행
		deque<int> dq;
		bool error = false;
		for (int i = 0; i < p.length(); i++) {
			if (p[i] == 'R') {
				// dq에 거꾸로 담기
				while(!q.empty()) {
					int temp = q.front();
					q.pop_front();
					dq.emplace_front(temp);
				}
				// q에 그대로 복사
				while (!dq.empty()) {
					int temp = dq.front();
					dq.pop_front();
					q.emplace_back(temp);
				}
			}
			else if (!q.empty() && p[i] == 'D')
				q.pop_front();
			else if (q.empty() && p[i] == 'D') {
				error = true;
				break;
			}
		}
		// 결과 출력
		if (error) cout << "error" << '\n';
		else {
			cout << '[';
			while(!q.empty()) {
				cout << q.front();
				q.pop_front();
				if (q.size() != 0)
					cout << ',';
			}
			cout << ']' << '\n';
		}
	}
}