글 읽기 - 시간초과가 나는 이유가 있을까요?

chy5948 7년 전 0

제가 생각해낸 해결법은 아래와 같습니다.

gets로 한줄 받은 후에 char포인터를 이용하는 방법입니다.

char포인터로 하나씩 검사하다가, 크로아티아 알파벳이 나오면 recursive(?)하게 크로아티아 알파벳이 어디까지인지 찾습니다.

크로아티아 알파벳이면 return 값을 받아서 현재 포인터를 이동시킵니다.

시간초과가 나는데 이유를 잘 모르겠네요.

#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <stdbool.h>

bool isCroatiaAlpha(char c) {
    if (c == 'c' ||c == 'd' ||c == 'l' ||c == 'n' ||c == 's' ||c == 'z') return true;
    return false;
}
int findNextPosition(char *p) {
    if (*p == 'z') return 1+ findNextPosition(p++);
    if (*p == '=' || *p == '-' || *p == 'c' || *p == 'j') return 1;
    return 0;
}
int main(int argc, const char * argv[]) {
    char ch[1001];
    char *ptr;
    int cnt = 0;
    gets(ch);
    ptr = &ch[0];
    while(*ptr != '\0') { //개행이 아닐때까지 루프를 돌립니다.
        int jumpIndex = 1;
        if (isCroatiaAlpha(*ptr)) { //크로아티아 알파벳인지 검사후
            jumpIndex += findNextPosition(ptr+1);
        }
        ptr = ptr + jumpIndex;
        cnt++;
    }
    printf("%d\n",cnt);
    return 0;
}

chy5948 7년 전 0

반례가 있었네요.

'cdz='의 경우 c에서 무한루프에 빠져서 시간초과가 나는거였네요.

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

문제

문제

출처

ICPC

시간초과가 나는 이유가 있을까요?

chy5948 7년 전 0

chy5948 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말