0-1 수열 O(n)인거 같은데 타임리밋뜨네요..

  • shim89
    shim89 
    #include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cstdio>
#include <cstring>

#define MAX_LEN 1000000
using namespace std;

int main()
{
  char arr_str[MAX_LEN];
  int i=0;
  int num_question=0;
  int num_A=0, num_B=0;

  scanf("%s", arr_str);//첫입력  

  int *group;
  group = new int [strlen(arr_str)];

  int group_cnt=0;
  for(i=0 ; i<strlen(arr_str) ; i++)
  {
    if(i==0)
    {
      group[i] = group_cnt;
    }
    else
    {
      if(arr_str[i] == arr_str[i-1])
      {
        group[i] = group_cnt;
      }
      else
      {
        group_cnt++;
        group[i] = group_cnt;
      }
    }
  }

  scanf("%d", &num_question);

  for(i=0 ; i<num_question ; i++)
  {
    scanf("%d %d", &num_A, &num_B);

    if(group[num_A] == group[num_B])
    {
      printf("Yes\n");
    }
    else
    {
      printf("No\n");
    }
  }

  return 0;
}

    12년 전
6개의 댓글이 있습니다.
  • JongMan
    JongMan

    아 입력 케이스 하나마다 O(n)이라고 말씀하시는 줄 알았는데 아니네요. 제가 처음 달았던 댓글에는 실수가 있었군요. 죄송 (__)

    TLE로 말할 것 같으면 구현상의 실수로 코드의 실제 시간 복잡도가 O(n)이 아닌 문제가 있으신 것 같네요 (kcm 감사)

    그리고 소스코드 포매팅 고쳐서 올려주세요 :)


    12년 전 link
  • shim89
    shim89

    아 죄송합니다... 그런데 어떤부분에 실제 복잡도가 O(n) 이상인 부분이나오는건가요?


    12년 전 link
  • Being
    Being

    strlen()의 구현이 어떤 식으로 되어 있을 지 생각해 보세요. :)


    12년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    strlen이 O(n) 입니다.


    12년 전 link
  • shim89
    shim89

    아하! 그렇군요 !!! 감사합니다 ㅎㅎ고쳐볼게요


    12년 전 link
  • Being
    Being

    맞으셨군요 :) 축하드려요~


    12년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.