글 읽기 - 반례를 못찾겠습니다

moon610 1년 전 0

시간초과라고 뜨는데 이건 코드는 맞는데 시간 복잡도를 초과해서 틀린건가요?

그게 아니라면 예제는 다 돌아가고 웬만해선 다 성립하는데 반례가 무엇인지 모르겠습니다

#include <stdio.h>
#include <ctype.h>
#include <string.h>
//1개때가 문제야//
int main(){
    char str[1000000];
    int cnt[26]={0,};
    fgets(str,sizeof(str),stdin);
    int i=0;
    while(str[i]!='\0'){
        str[i]=toupper(str[i]);
        i++;
    }
    if(strlen(str)<=2){
        printf("%c",str[0]);
    }
    else{
        int max=cnt[0];
        char temp=str[0];
        for(int j=0;j<strlen(str);j++){
            for(int k=j+1;k<strlen(str);k++){
                if(str[j]==str[k]){
                    cnt[j]++;
                }
            }
            if(cnt[j]>max){
                max=cnt[j];
                temp=str[j];
            }
            
        }
        int count=0;
        for(int p=0;p<26;p++){
            if(max==cnt[p]){
                count++;
            }
        }
        if(count==1){
            printf("%c",temp);
        }
        else{
            printf("?");
        }
    }
    return 0;
}

siyamaki 1년 전 1

20, 21번째줄에 str의 길이가 100만일때 100만 * 100만이므로 시간 초과 되는게 맞습니다.

알파벳 개수인 26칸짜리 배열을 만들고 입력된 char을 int로 변환 후 해당 값을 세서 최대값을 찾으면 됩니다.

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

문제

문제

출처

ICPC

반례를 못찾겠습니다

moon610 1년 전 0

siyamaki 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말