백준 #1157

#include <stdio.h>
#include <string.h>

#define MAX_LEN 1000001

int main() {
	char s[MAX_LEN];
	int counting[26] = {0, }, i, pos, max_count=0, max_pos=0;
	bool unique = true;

	// A = 65, a = 97
	scanf("%s", s);
	len = strlen(s);
	for (i = 0; i < strlen(s); i++) {
		if (s[i] < 97) pos = s[i] - 65;
		else pos = s[i] - 97;
		counting[pos]++;
		if (counting[pos] > max_count) {
			max_count = counting[pos];
			if (max_pos != pos) max_pos = pos;
			unique = true;
		}
		else if (counting[pos] == max_count) unique = false;
		if (s[i] == '\0') break;
	}

	if (unique == false) printf("?\n");
	else {
		max_pos += 65;
		printf("%c\n", max_pos);
	}

	return 0;
}

 백준 알고리즘 1157번을 풀다 시간초과로 실패했다. 분명 단일 for문으로 구현하였는데도 이와 같은 오류가 발생하여 코드를 다시 살펴보기로 했다.

 결론부터 말하면 for문 안의 조건문 i < strlen(s) 이 for문이 반복됨과 동시에 반복적으로 호출되기 때문이다. strlen() 함수는 인자 s가 가리키는 주소로부터 '\0'가 나올 때 까지의 문자들의 개수를 반환한다.

 만약 strlen()함수가 내부적으로 s가 가리키는 문자열의 길이 L만큼 반복하도록 구현되었다고 가정해보자. strlen(s)가 한 번 실행되는데 L번의 연산이 수행되고 for문 또한 L번 반복하므로 위 코드에서 strlen을 통한 연산 횟수는 총 L * L 번이다. 따라서 L이 1,000,000이라면 1,000,000^2번이라는 어마어마한 횟수의 연산을 수행하므로 시간초과가 발생할 수 밖에 없다.

 따라서 특정 문자열의 길이만큼 for문을 반복하도록 구현할 때에는 문자열의 길이를 저장할 수 있는 변수를 설정하고 strlen 함수가 한 번만 구현되도록 for문 밖에서 호출하는 것이 좋다.

 

#include <stdio.h>
#include <string.h>

#define MAX_LEN 1000001

int main() {
	char s[MAX_LEN];
	int counting[26] = {0, }, i, pos, len, max_count=0, max_pos=0;
	bool unique = true;

	// A = 65, a = 97
	scanf("%s", s);
	len = strlen(s);  // s의 문자열 길이를 len에 저장
	for (i = 0; i < len; i++) {  // strlen 대신 len 변수를 사용하자!!
		if (s[i] < 97) pos = s[i] - 65;
		else pos = s[i] - 97;
		counting[pos]++;
		if (counting[pos] > max_count) {
			max_count = counting[pos];
			if (max_pos != pos) max_pos = pos;
			unique = true;
		}
		else if (counting[pos] == max_count) unique = false;
		if (s[i] == '\0') break;
	}

	if (unique == false) printf("?\n");
	else {
		max_pos += 65;
		printf("%c\n", max_pos);
	}

	return 0;
}