인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

일단 로직 자체는 문제가 없습니다.

split, reverse, size체킹, pop 로직 정말 잘 짜셨네요.

네 다만 split에서 그런 시간초과가 나는 거 같습니다.

split을 잠깐보면

  while ((pos = input.find(delimiter)) != string::npos)
  {
    token = input.substr(0, pos);
    ret.push_back(stoi(token));
    input.erase(0, pos + delimiter.length());
  }

이렇게 되어있습니다. find 자체의 시간복잡도가 O(N)이기 때문에 이를 계속해서 실행하기 때문에 최악의 경우 O(N^2) 정도가 되버리기 때문에 그러는 것 같습니다.

해당부분을 이렇게 한 번 바꿔 볼까요?

    for(char c : str_num){
        if(c == '[' || c == ']') continue;
        // 숫자가 나오면 현재 수*10 한 뒤 더함
        if(c >= '0' && c <= '9') x = x*10 + c-'0';
        // 아닐 경우 현재 수를 덱에 넣음
        else{
            if(x > 0) numbers.push_back(x);
            x = 0; 
        }
    } 
    if(x > 0) numbers.push_back(x);

아 그리고

이 문제는 숫자 자체가 int형이 들어오기 때문에

    ret.push_back(stoi(token));

이렇게 쓰는 것이 좋습니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std;

int T;    // max 100
string p; // functions
int N;    // number of elements
string str_num;

deque<int> split(string input, string delimiter)
{
  // cout << "input = " << input << "\n";
  deque<int> ret;
  long long pos = 0;
  string token = "";

  while ((pos = input.find(delimiter)) != string::npos)
  {
    token = input.substr(0, pos);
    ret.push_back(stoi(token));
    input.erase(0, pos + delimiter.length());
  }

  if (input.length() > 0)
  {
    ret.push_back(stoi(input));
  }

  return ret;
}

int main(void)
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  cin >> T;

  while (T--)
  {
    deque<int> numbers;
    bool error = false;
    bool dir = true;
    cin >> p;
    cin >> N;
    cin >> str_num;
    int x = 0;
    for(char c : str_num){
        if(c == '[' || c == ']') continue;
        // 숫자가 나오면 현재 수*10 한 뒤 더함
        if(c >= '0' && c <= '9') x = x*10 + c-'0';
        // 아닐 경우 현재 수를 덱에 넣음
        else{
            if(x > 0) numbers.push_back(x);
            x = 0; 
        }
    } 
    if(x > 0) numbers.push_back(x);


    for (char func : p)
    {
      if (func == 'R')
      {
        dir = !dir;
      }
      else if (func == 'D')
      {
        if (numbers.size())
        {
          if (dir == true)
          {
            numbers.pop_front();
          }
          else
          {
            numbers.pop_back();
          }
        }
        else
        {
          error = true;
          break;
        }
      }
    }

    if (error)
    {
      cout << "error\n";
    }
    else
    {
      if (dir == false)
      {
        reverse(numbers.begin(), numbers.end());
      }

      cout << "[";

      for (int i = 0; i < numbers.size(); ++i)
      {
        cout << numbers[i];
        if (i < numbers.size() - 1)
        {
          cout << ",";
        }
      }

      cout << "]\n";
    }
  }

  return 0;
}

감사합니다.

split의 시간 복잡도는 n인것 같은데, 왜 최악의 경우일때, n^2인가요?