[덱]-응용-AC

< 덱 > - < 골드 5 >

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

5430번: AC

---

[ 5430 ] AC

 

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

 

:: 입력 ::

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

:: 출력 ::

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

---

 

풀이 밑에 있음

 

  정답  코드  

#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <string>

using namespace std;


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

	int t;
	cin >> t;

	string p;
	string nums;
	string num = "";

	int n;


	while (t--) {
		deque<int> q;
		bool isError = false, isReverse = false;

		cin >> p;
		cin >> n;
		cin >> nums;

		for (int i = 0; i < nums.length(); i++) {
			if (isdigit(nums[i])) {
				num += nums[i];
			}
			else {
				if (!num.empty()) {
					q.push_back(stoi(num));
					num = "";
				}
			}
		}

		for (char c : p) {
			if (c == 'R') {
				isReverse = !isReverse;
			}
			else {
				if (q.empty()) { isError = true; break; }
				if (isReverse) q.pop_back();
				else q.pop_front();
			}
		}

		if (isError) cout << "error\n";
		else {
			if (isReverse) {
				reverse(q.begin(), q.end());
			}
			cout << '[';
			for (int i = 0; i < q.size(); i++) {
				cout << q[i];
				if (i + 1 != q.size()) cout << ',';
			}
			cout << "]\n";
		}
	}
}

응용이라 그런지 문제가 어려웠다

 

처음에 [ 1, 2, 3, 4 ] 형태로 주어지는 입력을 처리하는 부분을 모르겠어서 그 부분을 빼고 기능 구현하고

잘 돌아가는 거 확인하고 저 입력 처리하는 부분은 구글링 해서 가져옴

 

주어진 예시에 맞는 출력이 나오길래 제출 해봤는데 시간 초과 걸렸고

R 명령이 들어올 때마다 진짜로 reverse 함수를 돌리는 게 원인 인 것 같아서

또다른 정답코드를 참고해서 reverse 상태를 체크하는 플래그만 만들어서 상태에 따라 pop_front / pop_back 을 하게 함

 

근데 틀렸대

그래서 이것저것 다 손대면서 고쳐봄

왜 틀렸는지 몰랐음 왜냐면 출력이 완벽했기 때문에 ,, 

 

그렇게 한 6번 정도 틀리고 화가 나서 정답 코드랑 비교해봤는데 출력하는 부분이 달랐음

그래서 출력하는 부분을 바꿨더니 맞음 ,,

 

위쪽이 내 원래 출력문이고

아래쪽이 정답코드의 출력함수인데

cout << '[';
            for (int k : q) {
                if (k == q.back()) {
                    cout << k;
                }
                else cout << k << ',';
            }
            cout << "]\n";

void print_result(deque<int>& d) {
    cout << '[';
    for (int i = 0; i < d.size(); i++)
    {
        cout << d[i];
        if (i + 1 != d.size())
            cout << ',';
    }
    cout << "]\n";
}

덱의 마지막 원소인지 확인하는 과정에서 q.back() 을 사용하면 안되는 것 같다

왜인지는 모르겠다

cout << '[';
			for (int k : q) {
				cout << k;
				if (k != q.back()) cout << ',';
			}
			cout << "]\n";

이런 형태로 해도 틀린다

진짜 힘들었다 ... 

 

제발 q.back()으로 마지막 원소인지 확인하면 안되는 이유가 뭔지 누가 좀 알려주세염

이거 알아냄 !! 값 비교개념이라 마지막 원소의 값이랑 다른 원소의 값이 같으면 예외 발생함 !!

 

1/16 - 또 시간 초과 해결 못해서 정답코드 참고 이번에는 로직까지 잘 찾고 숫자를 저장하는 부분도 혼자 해결했는데 reverse 연산 또 실제로 돌려버려서 시간초과 난 거 해결 못해서 정답 코드 봄 ,, 정답코드 읽으니까 전에 풀 때도 못해서 플래그 쓰는 거 참고했던 게 기억이 남 그래도 이번엔 출력부분 안 헤매고 바로 고칠 수 있었음

 

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

// 숫자를 저장할 deque
deque<int> dq;

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

   int t;
   cin >> t;
   
   for (int i = 0; i < t; i++) {
      // 수행할 명령
      string command;
      cin >> command;

      // 배열에 들어갈 숫자의 갯수
      int n;
      cin >> n;

      // 배열
      string arr;
      cin >> arr;
      
      // 에러인지 아닌지를 저장할 플래그
      bool isError = false;
      // 리버스 상태인지 아닌지를 저장할 플래그
      bool isReverse = false;

      // 입력 받은 배열에서 숫자만 뽑아내 dq에 저장
      /*for (char c : arr) {
         if (c == '[' || c == ']' || c == ',') continue;
         dq.push_back(c - '0');
         cout << c - '0';
      }*/
      // 위의 방식으로 숫자를 뽑아내면 예제의 42같은 두자리 숫자는 4랑 2로 나뉘어 들어가게 됨
      string str;
      for (int i = 0; i < arr.length(); i++) {
         if (arr[i] == '[' || arr[i] == ']' || arr[i] == ',') {
            if (str != "") {
               dq.push_back(stoi(str));
               str = "";
            }
            continue;
         }
         str += arr[i];
      }

      for (char com : command) {
         if (com == 'R'){
            //if (dq.size() == 1) continue;
            // 시간 초과를 피해보려는 알량한 노력 ,,
            // reverse(dq.begin(), dq.end());
            // 실제로 reverse 연산을 계속 수행하게 되면 시간초과 걸림
            // 플래그 활용
            isReverse = 1 - isReverse;
            // true -> false || false -> true
         }
         else if (com == 'D') {
            if (dq.empty() == true) { isError = true;  break; }
            else {
               if (isReverse) dq.pop_back();
               else dq.pop_front();
            }
         }
      }

      if (isError == true) { cout << "error\n"; }
      else {
         cout << "[";
         if (isReverse) {
            for (auto iter = dq.rbegin(); iter != dq.rend(); iter++) {
               if (iter == dq.rend() - 1) cout << *iter;
               else cout << *iter << ",";
            }
         }
         else {
            for (auto iter = dq.begin(); iter != dq.end(); iter++) {
               if (iter == dq.end() - 1) cout << *iter;
               else cout << *iter << ",";
            }
         }
         cout << "]\n";
      }
   
      dq.clear();
   }

}