[C, C++] strlen의 시간복잡도 (백준 3986: 좋은 단어)

<string.h> 안에 들어있는 strlen 함수

 

얘는 char str[500]; 같은 얘의 len을 구할 때 사용되는데

아마도 인덱스 0부터 NULL문자('\0')가 나올 때까지 무식하게 읽나 보다; 하긴 그거 말고 길이를 구할 방법이 없네

 

그래서 그런지 (문제에 따라 다르긴 하지만) for문안에 쓰면 시간초과가 나올 확률이 높다

 

원래는 나도 저런 정보를 for문안에 써야할때

무조건 변수로 빼줘서 저장하고 쓰는데,

 

한번 안 그랬다고 시간초과가 나서...

경각심을 가지기 위해..

 

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

int main() {
	int N;
	scanf("%d", &N);
	
	char row[100001];
	int ans = 0;
	while (N--) {
		scanf("%s", row);
		if (strlen(row) & 1) continue;
		stack<char> s;
		int mi = strlen(row);
		for (int i = 0; i < mi; i++) {
			if (s.size() > mi - i) break;
			if (s.empty()) s.push(row[i]);
			else if (s.top() == row[i]) {
				s.pop();
			}
			else {
				s.push(row[i]);
			}
		}
		if (s.empty()) ans++;
	}
	printf("%d", ans);
}

ㅋㅋ 이 문제 도대체 시간초과가 왜 나지 O(백만)인데 하면서

 

어떻게든 시간초과를 없애려고 노력한 부분

if (s.size() > mi - i) break;

 

하지만 이유는 그냥 N번 반복하는 for문에서

strlen을 사용했으므로

문자열 길이가 최대 100,000 이므로 N*100,000 이 된다.. 는 그런 거다

int mi = strlen(row);
for (int i = 0; i < mi; i++) {
    ...
}

int 변수 하나만으로도 개선되는 놀라운 시간 복잡도!

 

역시 자료구조를 많이 쓸수록(공간복잡도를 늘릴수록) 시간복잡도 및 알고리즘을 쉽고 간단화할 수 있다는 게 맞다

 

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

3986번: 좋은 단어