글 읽기 - 왜 시간초과인지 모르겠습니다. ㅠ

pch6789 4년 전 0

시간초과가 자꾸 나는데 왜 그런지 잘 모르겠습니다.

우선 제가 한 방식은 총 2개의 배열을 만들어서 숫자가 입력되었을 때와 문자열이 입력되었을 때 각기 다른 배열을 사용하도록 만들엇습니다.

숫자가 입력됐을 때 사용하는 배열의 경우 입력받은 그대로 사용하여 접근하는데 O(n)의 시간이 걸립니다.

문자열이 입력되었을 때 사용하는 배열의 경우 입력을 다 받은 후 정렬을 한번 진행하게 됩니다.
( 정렬에 소요되는 시간 O(n log n) )
이후 바이너리서치를 사용하여 찾게 됩니다. O(log n)

시간 복잡도가 O(n log n)이고 입력이 그렇게 크지 않은데 왜 시간초과가 발생하는지 잘 모르겠습니다. ㅠ
입력과 출력은 모두 scanf 와 printf를 사용했습니다.

도와주시면 감사하겠습니다.

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

char input[100000][25];     //24 == number;
char input_str[100000][25]; //24 == number;

int mycmp(char *a, char *b)
{
  for (int i = 0; i < 20; i++)
  {
    if (a[i] < b[i])
      return -1;
    else if (a[i] > b[i])
      return 1;
  }
  return 0;
}

int comp(const void *a, const void *b)
{
  return mycmp((char *)a, (char *)b);
}

int cstr_to_int(char *a, int size)
{
  int output = 0;
  for (int i = 0; i < size; i++)
  {
    output += a[i] - '0';
    output *= 10;
  }
  return output / 10;
}

void seek(char *a, int end)
{
  int start = 0;
  int mid;
  while (start <= end)
  {
    int mid = (start + end) / 2;
    int result = mycmp(input_str[mid], a);
    if (result == 0)
    {
      printf("%d\n", (int)input_str[mid][24] + 1);
      break;
    }
    else if (result < 0)
      start = mid - 1;
    else
      end = mid + 1;
  }
}

int main()
{
  // freopen("input.txt", "r", stdin);
  int n, m;
  scanf(" %d %d", &n, &m);
  for (int i = 0; i < n; i++)
  {
    scanf(" %s", input[i]);
    memcpy(input_str[i], input[i], sizeof(input_str[0]));
    input_str[i][24] = i;
  }
  qsort(input_str, n, sizeof(input_str[0]), comp);

  for (int i = 0; i < m; i++)
  {
    char temp[25];
    scanf(" %s", temp);
    if (temp[0] <= '9' && temp[0] >= '0')
      printf("%s\n", input[cstr_to_int(temp, strlen(temp)) - 1]);
    else
      seek(temp, n - 1);
  }

  return 0;
}

pch6789 4년 전 0

seek함수를 잘못 구현했습니다.

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

문제

문제

출처

ICPC

왜 시간초과인지 모르겠습니다. ㅠ

pch6789 4년 전 0

pch6789 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말