[12813번] 이진수 연산 (잘못된 strlen의 사용)

문제 출처 :

 

https://www.acmicpc.net/problem/12813

알고리즘 분석 :

문제 해결에 필요한 사항

-

이 문제를 통해 이해해 보고싶은 내용은

strlen에 관한 내용이다.

len = strlen(tmpa);라는 코드가 아닌

for문마다 i = 0; i < strlen(tmpa); i ++;가 들어왔다면 어떻게 되었을까?

필자도 이번 문제를 통해 너무 등한시 여겼던 오류를 느낀 것 같다.

strlen 또한 함수이며, 문제에서 10만바이트를 입력받는다 했으니 총 10만개가 입력될텐데

for문에서 strlen(tmpa)를 쓴다면

1번 돌때마다 strlen에 의해 10만번 돌고 이것이 tmpa의 길이만큼 즉 10만번 돈다면

100,000 * 100,000 = 10,000,000,000 (백억)이라는 시간이 소요된다.

즉 for문 한번당 백억이고, 5번의 for문이 있으니 O(500억)이 되어버린다.

이 문제로 인해 시간 초과가 뜨길레 처음에는 무슨 일인가 했고, 곰곰이 생각해보니 저런 치명적인 문제가 있었던 것이다.

만약 어떤 코딩을 할 때, 숏코딩을 위해 strlen을 쓰게 된다면 저러한 상황을 마주치지 않도록 유의해서 사용하자.

소스 코드 : 

#include <stdio.h>
#include <string.h>
 
int main()
{
    int a[100001];
    int b[100001];
    char tmpa[100001];
    char tmpb[100001];
    int i, len;
 
 
    scanf("%s", tmpa);
    scanf("%s", tmpb);
    
    i = strlen(tmpa) - 1;
    len = strlen(tmpa);
    
    while (i != -1)
    {
        a[i] = tmpa[i] - '0';
        b[i] = tmpb[i] - '0';
        i--;
    }
 
    for (i = 0; i < len; i++)
        printf("%d", a[i] & b[i]);
        printf("\n");
 
    for (i = 0; i < len; i++)
        printf("%d", a[i] | b[i]);
        printf("\n");
 
    for (i = 0; i < len; i++)
        printf("%d", a[i] ^ b[i]);
        printf("\n");
 
    for (i = 0; i < len; i++)
        printf("%d", !a[i]);
        printf("\n");
 
    for (i = 0; i < len; i++)
        printf("%d", !b[i]);
        printf("\n");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>