[Beakjoon, C++] 5430번 : AC

백준 단계별 풀기에서 큐,덱 일곱번째, 마지막 문제이다.
링크는 아래와 같다.

www.acmicpc.net/problem/5430

5430번: AC

 

---

백준 5430번 문제, 입력, 출력

---

백준 5430번 입출력 예제 1

---

1. 4가지를 입력 받는다, Testcase 개수를 우선적으로 받고, 각 Testcase 마다 RD연산 함수, 배열의 개수, 배열 3가지를 받는다. 일단은 배열을 어떤 타입으로 받을 것인지에 대한 고민이 필요하다. [x, y, z, q] 이런식으로 입력을 받아야 한다. 필자는 string으로 받아서 parsing을 통해 정수 배열로 만들어 줄 것이다. 일단 string으로 받게 되면 어떤식으로 들어오는지 확인해보자. 아래는 예시로 [1, 2, 3, 56] 을 받았을 때이다.

배열 [1, 2, 3, 56]의 메모리 구조

보다시피, 각각의 index는 char 타입으로 저장이 되고, 56이 각 각 다른 index에 '5'와 '6'으로 들어간다는 점을 인지하고 parsing을 해주어야 한다.

 

2. parsing을 하기 위해서 일단 정수들만을 1차적으로 걸러야 한다. seq[j] >= '0' && seq[j] =< '9' 의 조건으로 정수들을 빼낸다. 그리고 1자리 수가 아닌 n자리 수의 경우에 대한 연산이 필요하다. 56의 경우, 5*10+6 이런식으로, 123의 경우 1*10+2 ->12*10+3 이런식의 연산을 해주려고 한다. 

parsing 연산

3.  이제 RD 함수에 따라 parsing해서 넣은 deque(덱)을 처리하면 된다. 이번 문제가 어려웠던 것이 테스트 케이스는 최대 100개, RD함수의 개수 최대 10만개, 배열의 개수도 최대 10만개라는 점이였다. 그렇다면, 분명 연산을 하는 중에 오버플로우 또는 시간초과가 발생할 수 있을 것이라 예상하고 이것을 제어할 수 있어야 했다. 

 이제 RD함수로 돌아와 보자. string으로 RD함수(ex. RDDDRDRD, RRRDDR, ...)를 받기에 for문으로 한 index씩 읽어 갈 것이다. 여기서 R에 대해서 고민을 해보자. R을 받을 때마다 덱을 뒤집어야 할까? RR이 들어오면 결과적으로 이전과 같은데 굳이 R을 두번 수행할 필요가? 없다. 처음에 여기서 R을 받을때 마다 뒤집었더니, 오버플로우가 발생했다. 어떻게 제어를 해야할까? R을 받을때마다, flag역할을 할 bool타입 변수를 하나 두고 해당 값을 true-false 왔다갔다 바꿔준다. 그리고 D를 수행할때와 나중에 결과를 출력할 때, flag에 따라 2가지(true인 경우, false인 경우)로 처리를 하면 된다. 

 

4. error인 경우에 대한 처리. error인 경우는 deque(덱)이 비었는데 D를 수행하는 경우이다. D를 수행할 때, deque이 비었는지, flag가 true인 경우, false인 경우 이렇게 3가지로 처리를 한다. 여기서 deque이 비었다면 바로 error를 출력해도 되겠지만, R의 flag 변수를 둔 것과 마찬가지로, error flag변수를 둬서, error flag를 true로 만들어주고, 이후에 출력을 한다.

deque(덱) 출력 코드

위의 사진은 첫 시도에서 사용했던 deque을 출력하는 코드인데, 다음과 같이 deq이 비어있을 경우로 조건을 두었었다. 입력예제를 해보니 정상적으로 되었었다. 근데 왜 틀렸다고 하는 것일까? deque가 비었을 때 D를 하는 경우 error 인데, deque가 비었어도 D를 하지 않는 경우도 error로 간주하기 때문이였다. 따라서 아래의 예제 처럼 해주어야 한다. 

---

 

#include<iostream>
#include<deque>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int numOfTest;

    cin >> numOfTest;

    for (int i = 0; i < numOfTest; i++) {
        string funRD;
        int numOfSeq;
        string seq;
        bool isFront = true;
		bool isError = false;
        deque<int> deq;

        cin >> funRD;
        cin >> numOfSeq;
        cin >> seq;

        int indexOfseq = 1;
        while (seq[indexOfseq] != '\0') {
            bool isNum = false;
            int num = 0;

            while ((seq[indexOfseq] >= '0') && (seq[indexOfseq] <= '9')) {
                num *= 10; // 자리수 올려주기
                num += int(seq[indexOfseq] - '0'); // char형->int형 변환
                isNum = true;
                indexOfseq++;
            }
            if (isNum) {
                deq.push_back(num);
            }
            indexOfseq++;
        }
		
			for (int j = 0; j < funRD.size(); j++) {
				if (funRD[j] == 'R') {
					isFront = !isFront;
				}
				else if (funRD[j] == 'D') {
					if (deq.empty()) {
						isError = true;
						break;
					}
					else if (isFront) {
						deq.pop_front();
					}
					else {
						deq.pop_back();
					}
				}
			}
		

		if (!isError) {
			int resultDeqSize = deq.size();
			cout << "[";
			for (int i = 0; i < resultDeqSize; i++) {
				if (isFront) {
					cout << deq.front();
					deq.pop_front();
				}
				else {
					cout << deq.back();
					deq.pop_back();
				}

				if (i != resultDeqSize - 1) {
					cout << ",";
				}
			}
			cout << "]\n";
		}
		else {
			cout << "error\n";
		}

    }

    return 0;
}

---

이상으로 마지막 queue,deque문제를 마치겠다.