글 읽기 - [3111] 최악의 경우 O(n^2)만큼 도는 코드들이 통과됩니다.

#include <stdio.h>
char str[300001];
char pat[300001];
int g1=100000,g2=200000,g3=300000;
void tc1();
void tc2();
void tc3();
int main(void)
{
    tc1();
    printf("%s\n%s",pat,str);
}
//to generate test_case
void tc1()
{
    pat[0] = 'a';
    for(int i=0;i<g1;i++)
        str[i] = 'a';
    for(int i=g1;i<g2;i++)
        str[i] = 'b';
    for(int i=g2;i<g3;i++)
        str[i] = 'a';
}
void tc2()
{
    pat[0] = 'b';
    for(int i=0;i<g1;i++)
        str[i] = 'a';
    for(int i=g1;i<g2;i++)
        str[i] = 'b';
    for(int i=g2;i<g3;i++)
        str[i] = 'a';
}
void tc3()
{
    pat[0] = 'a';
    for(int i=0;i<g1;i++)
        str[i] = 'a';
    for(int i=g1;i<g2;i++)
        str[i] = 'b';
    for(int i=g2;i<g3;i++)
        str[i] = 'b';
}

eric00513 5년 전 2

O(n²)이 통과한다는게 신기하네요

chogahui05 5년 전 2

사실 StringBuilder의 Delete도 꽤 빠르게 동작하긴 하더라고요..

내부적으로 배열이라고 한다면.. 꽤 빠른 편인데..

평균값으로 아무리 계산해보아도 이론적으로는 O(n^2)라.. charAt()가 Constant인 것도 그렇고..

하여튼 StringBuilder를 가지고 단순하게 IndexOf, LastIndexOf, delete를 하는 건 문제에서 요구하는 풀이도 아닐 뿐더러. 데이터 크기를 보았을 때

올바른 풀이가 아니어 보입니다.

startlink 5년 전 0

재채점했습니다.

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

문제

문제

출처

ICPC

[3111] 최악의 경우 O(n^2)만큼 도는 코드들이 통과됩니다.

chogahui05 5년 전 2

eric00513 5년 전 2

chogahui05 5년 전 2

startlink 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말