[백준/BOJ] 5430번 AC (C++)

www.acmicpc.net/problem/5430

5430번: AC

많은 시행착오를 겪은 문제, 자료구조의 기본개념과 시간복잡도 고려의 중요성을 깨닫게 해준 아주 좋은 문제였습니다.

숫자가 두자리 이상일 수 있다는 점과 reverse 함수를 사용할 시 시간복잡도가 100,000 * 100,000 = 10,000,000,000 로 1초가 넘어가기 때문에 시간오류가 발생할 수 있다는 점을 주의합시다.

 

이러한 시간 초과를 해결하기 위해서 먼저 덱을 선언하여 입력받은 문자열에서 숫자만 따로 파싱하여 저장했습니다. 그리고 정방향과 역방향을 나타내는 bool 변수 flag를 두어 flag = true 정방향일 때는 맨 앞의 원소를 제거하고, 역방향일 때는 맨 뒤의 원소를 제거합니다. 마지막으로 출력을 할 때 정방향이면 덱이 빌 때까지 맨 앞 원소를 출력하고 pop합니다. 반대로 역방향이면 덱이 빌 때까지 맨 뒤 원소를 출력하고 pop합니다.

 

이러한 동일한 문제 풀이를 가지고 덱 대신에 벡터를 사용해도 답이 나올까 실험해봤는데, 벡터를 이용하면 역시나 시간초과가 발생하는 것을 확인할 수 있었습니다. 그 이유는 벡터의 특정 원소를 삭제하게 되면 빈 자리를 채우기 위해서 인덱스가 한칸씩 땡겨지는데, 이러한 과정에서 역시나 reverse와 마찬가지로 O(N)의 시간복잡도를 가질 수 있기 때문입니다. 따라서 해당 문제를 해결하기 위해서는 반드시 덱이나 리스트 자료구조를 사용해야합니다.

 

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int t;
    cin>>t;
    while(t--) {
    	string p;
    	cin >> p;
    	
    	int n;
    	cin >> n;
    
    	string numArr;
    	cin >> numArr;
    	
    	deque<int> dq;
    	string tmp = "";
    	
    	for(int i = 0; i < numArr.size(); i++) {
    		if(numArr[i] == '[') {
    			continue;
			} else if(numArr[i] >= '0' && numArr[i] <= '9') {
    			tmp += numArr[i];
			} else if(numArr[i] == ',' || numArr[i] == ']') {
				if(!tmp.empty()) {
					dq.push_back(stoi(tmp));
					tmp.clear();
				}
			}
		}
		
		bool flag = true; // 정방향 == true, 역방향 == false 
		bool isEmpty = false;
		for(int i = 0; i < p.size(); i++) {
			if(p[i] == 'R') {
				flag = !flag; // 방향 변경 
			} else {
				if(!dq.empty()) {
					if(flag) {
						dq.pop_front();
					} else {
						dq.pop_back();
					}
				} else {
					isEmpty = true;
					cout << "error\n";
					break;
				}
			}
		}
		 
		if(!isEmpty) {
			cout<<"[";
			if(flag) {
				while(!dq.empty()) {
					cout << dq.front();
					dq.pop_front();
					if(!dq.empty()) cout<<",";
				}
			} else {
				while(!dq.empty()) {
					cout << dq.back();
					dq.pop_back();
					if(!dq.empty()) cout<<",";
				}
			}
			cout << "]\n";
		}
	}
}