글 읽기 - 에디터, C++) 시간초과 도와주세요 ㅠㅠ

nopanderer 7년 전 0

어떤 부분이 문제일까요 ㅠㅠ 고수분들 부탁드립니다.

#include <iostream>
using namespace std;

int main()
{
  char input[600001];
  char cmd[10];
  int num;
  int cur = 0;
  int size = 0;

  cin.getline(input,600001);

  int i = 0;
  while(input[i++] != '\0'){
    size++;
  }
  cur = size;
  cin>>num;
  cin.ignore();

  while(num-- > 0){
    cin.getline(cmd,10);
    switch(cmd[0]){
      case 'L':
        if(cur != 0)
          cur--;
        break;
      case 'D':
        if(cur != size)
          cur++;
        break;
      case 'B':
        cur--;
        for(int i = cur; i < size - 1; i++)
          input[i] = input[i+1];
        size--;
        break;
      case 'P':
        for(int i = size - 1; i >= cur; i--)
          input[i+1] = input[i];
        input[cur++] = cmd[2];
        size++;
        break;
    }
  }
  for(int i = 0; i < size; i++)
    cout<<input[i];
  cout<<endl;

  return 0;
}

mixnuts 7년 전 1

1. 위 코드에서 B, P 연산의 시간 복잡도는?
> 문자열 길이를 $L$이라고 했을 때, $O(L)$.

2. 그렇다면 위 코드의 시간 복잡도는?
> 쿼리 수를 $Q$, 중간 연산 과정에서 문자열 길이의 최대를 $L$이라 하면,
> 최악의 경우, B/P연산만 반복해서 들어올 수 있으므로 $O(LQ)$.

3. $O(LQ)$는 대략 어느정도?
> $L = 10^5$, $Q = 5 \times 10^5$ 이므로 $5 \times 10^{10}$.
> 컴퓨터가 대략 1초에 $2 \times 10^{8}$번 처리하므로 위 소스는 250초는 걸리겠군요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

에디터, C++) 시간초과 도와주세요 ㅠㅠ

nopanderer 7년 전 0

mixnuts 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말