백준) strlen을 for loop 조건문에 넣어서 시간 초과가 뜨는 경우(C언어)

codingfeature 2023. 7. 29. 19:06

1157번: 단어 공부

알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다.

www.acmicpc.net

위 문제를 푸는 동안 답은 맞지만 계속 시간 초과가 떠서 헤메다가 질문 게시판에서 발견한 답변이 있는데 잘못하면 놓치기 쉬운 디테일인 것 같다.

// 시간 초과.
for(i=0;i<strlen(str);i++){
    if(str[i] >= 'a' && str[i] <= 'z')
        ABC[str[i]-'a']++;
    else if(str[i] >= 'A' && str[i] <= 'Z')
        ABC[str[i]-'A']++;
}

// 시간 초과 발생 X
int l = strlen(str);
for(i=0;i<l;i++){
    if(str[i] >= 'a' && str[i] <= 'z')
        ABC[str[i]-'a']++;
    else if(str[i] >= 'A' && str[i] <= 'Z')
        ABC[str[i]-'A']++;
}

문자열의 크기가 매우 크다면 for 문 내 조건 안에 strlen 함수를 넣느냐 밖에 넣느냐에 따라 런타임이 크게 달라지는 것을 알게되었다. for loop을 돌릴때마다 조건문 내 연산이 수행되면서 strlen() 함수를 문자열 크기만큼 반복해서 호출해서 발생하는 문제인 것 같다. 만약에 문자열의 크기가 1,000,000이라면 strlen 함수를 1,000,000번 호출하는 것이다.

for문 내 조건문에 쓰이는 함수는 밖에서 사용해야겠다.