반복문의 조건문 안에 strlen을 넣지 마세요.

C/C++에서 strlen은 char의 연속으로 이루어진 기초적인 형태의 문자열의 길이를 구해주는 역할을 합니다. 문자열의 구조를 몰라도 strlen만 있으면 손쉽게 길이를 알 수 있으니 참으로 편리한 함수이지만, 구조를 모르고 아무 곳에나 사용하면 다음과 같은 문제를 겪게 될 수 있습니다.

 

문자열을 다루는 문제에서 "문자열의 모든 문자를" 하나씩 전부 확인해야 하는 경우가 있습니다. 이 경우 가장 일반적인 방법은 아래와 같이 for 루프를 도는 것입니다.

 

char str[1000001];
scanf("%s", str);

for (int i = 0; i < str의_길이; i++)
{
	str[i]에_대한_연산;
}

 

str의 최대 길이가 100만인 문제에서, str의_길이를 구하기 위해 다음과 같이 코드를 작성하면 대부분 시간 초과를 받게 됩니다.

 

char str[1000001];
scanf("%s", str);

for (int i = 0; i < strlen(str); i++)
{
	str[i]에_대한_연산;
}

 

겨우 strlen(str)라는 아주 짧은 한 문장을 적었을 뿐인데 대체 이게 왜 시간 초과가 될까요? 문자열의 길이를 구하는 것이 그렇게나 느린 연산일까요? 이는 반만 맞는 이야기입니다. 사실 문자열의 길이를 구하는 것 자체는 그렇게 느리지 않습니다. 문제가 되는 것은 이를 반복문의 조건문에 넣었다는 부분입니다.

 

우선 strlen(str)가 동작하는 방식을 알아야 합니다. char의 연속으로 이루어진 문자열은 문자들이 연속으로 쭉 있다가 널 문자('\0')로 끝나는 형태로 구성되어 있습니다. 문제는, 이 널 문자를 발견하기 전까지 strlen이 할 수 있는 일은 그저 한 글자씩 나아가면서 전부 확인하는 것밖에 없다는 것입니다. 그래서 문자열의 길이를 $N$이라고 하면, strlen은 널 문자 포함$N+1$개의 문자를 전부 읽어보는 수밖에 없고, 그래서 한 번에 실행되는 데에 걸리는 시간 복잡도는 $\mathcal{O}(N)$이 됩니다.

 

그 다음 for 루프의 동작을 알아야 하는데, 자세한 설명은 생략하고 이 코드에서 문제가 되는 부분만 살펴보겠습니다. 조건문은 for문이 한 바퀴 돌 때마다 매번 실행되기 때문에 strlen도 루프가 한 번 돌 때마다 매번 꼬박꼬박 실행됩니다. 그런데 루프 자체가 문자열의 길이, 즉 $\mathcal{O}(N)$ 번을 도는 코드입니다. 한 번 실행하는 데에 $\mathcal{O}(N)$의 시간이 걸리는 코드를 $\mathcal{O}(N)$ 번을 실행하니, 루프 전체에 대한 시간 복잡도는 $\mathcal{O}(N^2)$이 됩니다.

 

100만의 제곱은 1조로, 아무리 1초에 약 10억 번을 연산하는 빠른 채점 서버라고 할지라도 이러한 문제들에서 통과를 기대하기에는 무리가 있을 것입니다.

 

이에 대한 해결 방법은 간단합니다. 아래와 같이 strlen이 한 번만 실행되도록 미리 길이를 따로 구해두면 됩니다.

 

char str[1000001];
scanf("%s", str);

int len = strlen(str);
for (int i = 0; i < len; i++)
{
	str[i]에_대한_연산;
}