글 읽기 - 분명 잘 돌아가는데, 계속 틀렸다고 나옵니다.(브론즈1)

jjjooo48 1년 전 0

문제가 뭔지 알려주세요.

분명 테스트케이스를 계속 돌려도 다 성공이던데, 왜 채점시스템에서는 '틀렸습니다'가 뜰까요?

런타임에러도.. 메모리 초과도...아닌 정말 반례가 있는 걸까요..

몇시간째 붙잡고 있다가 글 올립니다.

//1157번
#include <iostream>
#include <cstring>
using namespace std;

int main(){
    char str[100];
    cin>>str;
    
    int dat[1000]={0};
    for(int i=0;i<strlen(str);i++){
        dat[str[i]]++;
    }
    //대문자에 몰아주고, 소문자는 생각 x
    for(int i=65;i<=90;i++){
        dat[i]= dat[i]+dat[i+32];
    }
    //큰거 찾아
    int max=0;
    char maxvalue='a';
    for(int i=65;i<=90;i++){
        if(dat[i]>max){
            max=dat[i];
            maxvalue=char(i);
        }
    }
    
    int count=0;
    for(int i=65;i<=90;i++){
        if(max==dat[i]) count++;
    }
    if(count>1) cout<<'?';
    else cout<< maxvalue;
    
    return 0;
}

dh0450 1년 전 1

단어의 길이는 1,000,000을 넘지 않는다.

arr 배열 길이를 늘려주세요

jjjooo48 1년 전 0

감사합니다 !

그런 이유가 있었군요!

+ 시간초과 문제 해결을 위해 int len=strlen(str); 처리 해주었습니다.

근데 왜 이렇게 코드를 작성하면 시간복잡도가 줄어드는 건가요?

dh0450 1년 전 1

for(A; B; C) {D} 는 처음 A 식을 수행하고

B가 참인지 파악하고 D 를 수행한 하고 C 를 수행 후 다시 B가 참인지 평가하는 루틴을 반복합니다.

이때 B 가 함수라면 함수를 매번 호출하게 되는데, 문자열 길이를 파악하는 strlen() 은 시간복잡도가 아마 O(N) 으로 보입니다.

그래서 기존코드는 시간복잡도가 O(N^2) 가 됩니다.

jjjooo48 1년 전 0

감사합니다! 많이 알아가네요 ㅎㅎ

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

문제

문제

출처

ICPC

분명 잘 돌아가는데, 계속 틀렸다고 나옵니다.(브론즈1)

jjjooo48 1년 전 0

dh0450 1년 전 1

jjjooo48 1년 전 0

dh0450 1년 전 1

jjjooo48 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말