백준/5430번, AC/C++

백준 5430번 AC c++ 문제풀이

문제 설명

배열이 주어지면 해당 배열을 뒤집거나(R), 처음 숫자를 버리는 연산(D)을 시행한 뒤 최종 결과를 출력한다.

주의할 점

1. 실제로 배열을 뒤집을 생각을 하면 시간초과의 길로 빠지게 된다. 배열의 실제 순서는 상관 없다는 것을 깨달으면 문제가 비교적 쉽게 풀린다.
2. c++의 string에는 split 함수가 없기 때문에 직접 구현하거나, find를 써야 한다. 입력형태가 독특하다는 점을 유의해야 한다.

생각의 흐름

1. 배열을 매번 뒤집으면 시간 초과가 날테니까 덱을 써서 현재 진행 방향에 따라 front나 back으로 다르게 접근하는 게 좋겠다.
2. 비어있는데 에러인 경우나 진행 방향은 bool형 변수를 두어서 확인해야겠네
3. split 없는데 직접 구현하기 귀찮다.. 근데 find 쓰면 시간복잡도 O(N)이라 뭔가 시간초과될까봐 무서우니까 직접 구현해야지

코드

#include <iostream>
#include <string>
#include <deque>
#include <sstream>

using namespace std;

deque<int> split(string input, char delim){
  deque<int> answer;
  stringstream ss(input);
  string temp;

  while(getline(ss, temp, delim)){
    answer.push_back(stoi(temp));
  }

  return answer;
}

int main(void)
{
  int T;
  cin >> T;

  for(int i = 0; i<T; i++){
    string p, s, num;
    int n;
    cin >> p >> n;
    cin >> s;
    deque<int> nums = split(s.substr(1,s.size()-2),',');
    bool isDesc = false;
    bool errorFlag = false;

    for(char c : p){
      if(c == 'D' && nums.empty()){
        errorFlag = true;
        break;
      }
      else if(c == 'D' && !isDesc){
        nums.pop_front();
      }
      else if(c == 'D' && isDesc){
        nums.pop_back();
      }
      else {
        isDesc = !isDesc;
      }
    }

    if(errorFlag){
      cout << "error\n";
      continue;
    }

    cout << "[";

    for(int j = nums.size(); j>1; j--){
      if(isDesc){
        cout << nums.back() << ",";
        nums.pop_back();
      }
      else{
        cout << nums.front() << ",";
        nums.pop_front();
      }
    }

    if(!nums.empty())
      cout << nums.front();

    cout << "]\n";
  }
}

디버깅 기록

1. 모든 연산을 수행한 후 빈 배열인 경우를 제대로 처리를 안 해줘서 틀렸었다. 예시로 주어진 입력을 최대한 활용해 다양한 경우를 파악하고, 예시 입력에서 더 나아가서 훨씬 다양한 경우의 입력을 스스로 깨닫고 파악하는 연습이 더 필요할 듯.
2. c++을 주언어로 선택해놓고 기본적으로 string을 split하는 방법조차 마련해두지 않았다는 것에 부끄러움을 느꼈다.. find로 쓰든지, 일일이 경우의 수를 나누어서 걸러내든지, 이번처럼 stream으로 직접 split을 구현하든지 string을 split하는 여러 방법에 조금 더 익숙해지도록 노력해야지.
3. 나는 이게 덱으로 풀 수 있는 문제라는 걸 알고 풀었는데, 아마 그걸 몰랐다면 배열을 직접 뒤집으려고 하다가 많이 고생했을 거다. 문제가 하라는대로 구현하는 것에 너무 익숙해져있다. 최소한의 연산으로 답을 구하는 방법을 찾도록 하자.