strlen 힘수의 시간복잡도는 O(n) 입니다. 1번 소스에서와 같이 strlen 을 for문 안에 넣게 되면 시간복잡도는 적어도 O(n^2) 가 됩니다.
1157번 - 단어 공부
대소문자를 구분하지 않고 문제를 푼다는 건 말도 안 되고요, 시간초과의 문제는 윗 분 말씀대로 혹은 두 번째 소스코드에 적으신대로 int나 unsigned int 변수에 strlen() 함수를 호출해서 얻은 결과를 저장하면 해결됩니다.
문제는 "틀렸습니다"인데, 틀렸습니다는 시간초과 때문에 발생하는 문제가 아닌 구현하신 루틴이 잘못되었기 때문입니다.
제 추측컨데 문제가 발생하는 코드는 이 부분이라고 생각합니다. (두 번째 소스코드 기준)
max = a[1], k[1] = 1;
for (i = 2; i <= 26; i++)
if (max <= a[i]) max = a[i], k[++cnt] = i;
if (cnt == 1) printf("%c", k[1] + 64);
else printf("?");
return 0;
예를 들어 aBb 같은 문자열이 주어지게 되면 현재 알파벳 개수가 제일 많은 건 'A'라고 선택된 상태인데, B의 개수가 A보다 많게 되므로 cnt값이 올라가게 됩니다.
그러므로 위의 경우에는 cnt가 1이 아니게 되어 B라고 출력되어야 할 것이, ?라고 표시되는 것입니다.
위의 코드를 짜실 때 어떤 생각으로 짜셨는진 잘 모르겠습니다만, 알파벳 범위만큼 돌면서 최대값을 확보하신 뒤에 그 최대값과 겹치는 (그러니까 최대값이 같은) 알파벳 개수가 있으면 ?를 출력하도록 만드는 건 어떨까요?
@gallopsys님, 그렇게 하면 대신 시간복잡도는 O(n) 만큼 늘어나겠네요? (최악의 경우에)
아 맞다 특히 @gallopsys님, @bupjae님, 모두 감사합니다
댓글을 작성하려면 로그인해야 합니다.
eric00513 5년 전
제가 아래 소스 같이 풀어보았는데, 변수 len 하나 잡아서 문자열 길이를 저장했을 뿐인데, 왜 결과가 1번 코드: 시간 초과, 2번 코드: 틀렸습니다 로 다를까요?
참고: 1번 코드, 2번 코드