큐,덱 - 백준 5430번 AC

www.acmicpc.net/problem/5430

5430번: AC

IDEA

다신 만나고싶지 않다,,,,

이렇게 문자열 처리?로 시작하는 거 너무 힘들어.,,,,

 

R 이면 숫자를 뒤집고 , D면 맨 앞에 있는 숫자를 버리는 걸 반복해 최종 결과를 출력하는 문제이다.

문제에서 배열을 뒤집으라고 했다가 뒤집으면 인생이 피곤해진다. 

• 뒤집은 결과물을 출력하는 거기 때문에, 몇 번 뒤집혔냐에 따라 앞에서부터 출력하느냐, 뒤에서부터 출력하느냐의 문제이기때문에 deque 덱을 써야한다. 
  
  
• string으로 배열을 입력받는다.
  str[i] 가 수라면 temp에 저장해둔다.   98같은 두자리 이상의 숫자를 숫자로 받아줘야하기때문이다.
  수가 아니라면 이전에 temp에 저장해뒀던 수들을 뒤에서 하나씩 꺼내가면서 10을 곱해주어 숫자로 만들어 덱에 넣어준다.  
  
  
• 명령어가 D 일 때, 만약 덱이 비어있다면 더 뺄 것이 없으므로 STOP = TRUE; 를 만들어주어 ERROR가 출력될 수 있도록 만들어준다.
  
  
• 명령어가 D일 때, 덱이 비어있지 않다면 REVERSE를 고려해 빼준다. 
  REVERSE가 FALSE인 경우, 뒤집히지 않았다는 뜻이기때문에, 앞에서부터 POP을 해줘야하므로 FRONT_POP사용
  REVERSE가 TRUE인 경우, 뒤집혔다는 뜻이기에 뒤에서부터 BACK_POP을 사용해준다. 
  
  
• 명령어가 R일 경우, 뒤집혀야하기때문에 REVERSE가 TRUE라면 FALSE로, FALSE라면 TRUE로 바꿔준다. 

 

신경을 못 써 틀렸던 반례들이 두가지 있었다. 

 

첫 번째는 명령어가 d인데 덱이 비어져있는 상황에서 바로 ERROR를 출력했었다. 

그러면 뒷쪽에서 한 번 더 걸려 [ ] 같은 게 출력이 되기때문에 뒷쪽 출력과정에서 STOP 의 참.거짓에 따라 조건문을 사용해주었다. 

 

두번째는 모든 명령을 끝내고 나니 비어져있을 때다. 

DRD

2

[1,2] 

같은 상황에선 모든 명령을 끝내고 나면 덱이 비어져있게 된다. 

그렇기 때문에 출력을 하기 전 덱이 비어져있는 지 확인하고 비어져있다면 괄호만 출력하도록 해줘야한다. 

CODE

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

deque<int> dq;
vector<int>temp;

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int tc;
	cin >> tc;
	for (int z = 0; z < tc; z++) {
		//주문 , n , 배열  입력받기
		string order, str;
		int n;
		cin >> order >> n >> str;
		for (int i = 0; i < str.size(); i++) {
			if (0 <= str[i] - '0' && str[i] - '0' < 10) {
				temp.push_back(str[i] - '0');
			}
			else {
				int ten = 1, num = 0;
				while (!temp.empty()) {
					num += temp.back() * ten;
					temp.pop_back();
					ten *= 10;
				}
				if (num) dq.push_back(num);
			}
		}

		//주문에 따라 행동 
		bool reverse = false;
		bool stop = false;
		for (int i = 0; i < order.size(); i++) {
			if (order[i] == 'D' && dq.empty()) { //빼야되는데 빈 상황 -> error 출력
				stop = true;
				break;
			}
			else if (order[i] == 'D' && !dq.empty()) { //reverse 상태 확인 후 앞/뒤에서 뺌 
				reverse == false ? dq.pop_front() : dq.pop_back();
			}
			else reverse == false ? reverse = true : reverse = false; //reverse 상태 변화
		}
        //출력
		if (stop)  cout << "error" << "\n";
		else {
			if (dq.empty()) cout << "[" << "]" << "\n";
			else {
				//모든 ORDER를 실행한 후 EMPTY일때를 고려해줘야함 !!
				if (reverse && !stop) { // reverse 된 상황이라면 뒤에서 부터 빼내서 출력
					cout << "[";
					while (dq.size() > 1) {
						cout << dq.back() << ",";
						dq.pop_back();
					}
					cout << dq.back() << "]" << "\n";
					dq.pop_back();
				}
				else if (!reverse && !stop) {
					cout << "[";
					while (dq.size() > 1) {
						cout << dq.front() << ",";
						dq.pop_front();
					}
					cout << dq.back() << "]" << "\n";
					dq.pop_front();
				}
			}
		}
	}
}