[백준] 5430번 : AC (C++)

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

5430번: AC

문제 자체는 쉬운것 같았다. 그냥 구현이겠거니 vector를 사용해서 reverse()함수를 통한 뒤집기를 해보니.... 시간초과가 떠버렸다. (이렇게 쉽게 풀릴리가 없지...)

 

 

다음으로 시도한 방식은 자료구조 덱(deque)을 사용하는 것이다. 

R이 나올때마다 매번 reverse를 하면 엄청나게 비효율적일 것이므로, 정방향인지 역방향인지 상태를 나타내는 bool형 dir변수를 두었다. 

dir가 true면 정방향이므로, D가 나올때 pop_front()를 해주고 false면 역방향이므로 pop_back()을 해주었다.

 

다시 제출을 해보았다. 결과는 ....................

 

틀렸습니다!! 

 

알고보니, 주어지는 숫자가 꼭 한자리라는 법이 없었다. 그전에는 for문으로 한자리씩 받았었다. 물론 테스트케이스도 통과했다. (테스트 케이스를 믿지말자..) 1~100까지 숫자가 있으므로, 한자리씩 끊어서 덱에 넣는 것이 아닌, 콤마를 기준으로 숫자를 모두 읽은 후에 넣어야했다. 

 

알고보면 쉬운문제였던거 같은데 왜이렇게 헤맸는지 모르겠다. 앞으로 문제 조건을 더 꼼꼼히 읽고 테스트 케이스를 너무 믿지 말아야겠다. 이런 AC 😡😡

 

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

int T, N;
string P,n; //함수 & 배열

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> T;
	while (T--) {
		cin >> P; cin >> N; cin >> n;
		deque<int> dq;
		bool dir = true; //정방향 역방향 여부
		bool flag = true; //정상 여부
		string temp="";
		for (int i = 1; i < n.size(); i++){ 
			if (n[i] == ',' || n[i]==']') {
				if(temp!="") dq.push_back(stoi(temp)); //str -> int
				temp = "";
			} else temp += n[i]; //꼭 한자리 숫자 아님
		}

		for (int i = 0; i < P.size(); i++){
			if (P[i] == 'R') { //방향 뒤집기
				dir = !dir;
			}
			else if (P[i] == 'D') { //빼기
				if (dq.empty()) {
					flag = false; //비정상
					break;
				}
				else {
					if (dir) dq.pop_front(); //정방향
					else dq.pop_back(); //역방향
				}
			}
		}
		if (!flag) cout << "error" << endl;
		else {
			if (!dir) reverse(dq.begin(), dq.end()); //역방향이면 뒤집기
			cout << "[";
			for (int i = 0; i < dq.size(); i++){
				if (i == dq.size() - 1) cout << dq[i];
				else cout << dq[i] << ",";
			}
			cout << "]" << endl;
		}
	}
}