글 읽기 - 시간초과가 왜 뜨는지 이유를 모르겠습니다.

ae04071 7년 전 1

아래 코드로 했는데 시간초과가 뜨네요.

64~71, 72~79번 라인을 각각

for(int i = 0; i < n; i++)

{

scanf(" %c", &ch);

p.push_back(ch);

}

for(int i = 0; i < n; i++)

{

scanf(" %c", &ch);

s.push_back(ch);

}

이런식으로 scanf를 쓸 때 %c 앞에 띄어쓰기를 해주고 입력을 받으면 문제없이 맞으니 뭐가 틀리는지 이유를 모르겠네요 ㅜ

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>

std::string s, p;
int n, m;
int pi[1000001];
int cnt;

void GetPi()
{
    int j = 0;
    for(int i = 1; i < p.size(); i++)
    {
        while(j > 0 && p[i] != p[j])
            j = pi[j-1];
        if(p[i] == p[j])
            pi[i] = ++j;
    }
}

void kmp()
{
    int j = 0;
    for(int i = 0; i < s.size(); i++)
    {
        while(j > 0 && s[i] != p[j])
            j = pi[j-1];
        
        if(s[i] == p[j])
        {
            if(j == n-1)
            {
                j = pi[j];
                cnt++;
            }
            else
            {
                j++;
            }
        }
    }
}

void Result()
{
    int a = cnt, b = n;
    while(a != 0)
    {
        int t = b % a;
        b = a;
        a = t;
    }
    printf("%d/%d\n", cnt/b, n/b);
}

int main()
{
    char ch;
    
    scanf("%d", &n);
    m = n;
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &ch);
        if('A' <= ch && ch <= 'Z')
            p.push_back(ch);
        else
            i--;
    }
    for(int i = 0; i < n; i++)
    {
        scanf("%c", &ch);
        if('A' <= ch && ch <= 'Z')
            s.push_back(ch);
        else
            i--;
    }
    s += s;
    s.pop_back();
    
    GetPi();
    kmp();
    
    Result();
    
    return 0;
}

zych1751 7년 전 0

인풋에 소문자가...

ae04071 7년 전 0

??????? 이런 함정이...

choyungsoo 7년 전 0

이 문제를 푸는데 틀렸습니다가 떠서 질문검색을 봤는데 제 풀이 방식이랑 같네요

제가 틀린 이유가 81라인의 s.pop_back() 이 처리를 안해줘서 틀렸는데요

이 처리를 왜 해주는 건가요?

ae04071 7년 전 0

제 코드로 설명해드리면

s의 문자열로 abc가 들어오고 p의 문자열도 abc가들어오면

s+=s했을떄 abcabc 이렇게되서 abc를 두 번 셉니다.

이런거 방지할려고 pop_back 해준거 같아여 ㅎ

choyungsoo 7년 전 0

아 그러네요 ㅎㅎ

감사합니다!

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

문제

문제

출처

ICPC

시간초과가 왜 뜨는지 이유를 모르겠습니다.

ae04071 7년 전 1

zych1751 7년 전 0

ae04071 7년 전 0

choyungsoo 7년 전 0

ae04071 7년 전 0

choyungsoo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말