eric00513   5년 전

제가 아래 소스 같이 풀어보았는데, 변수 len 하나 잡아서 문자열 길이를 저장했을 뿐인데, 왜 결과가 1번 코드: 시간 초과, 2번 코드: 틀렸습니다 로 다를까요?

참고: 1번 코드, 2번 코드

bupjae   5년 전

strlen 힘수의 시간복잡도는 O(n) 입니다. 1번 소스에서와 같이 strlen 을 for문 안에 넣게 되면 시간복잡도는 적어도 O(n^2) 가 됩니다.

eric00513   5년 전

그러면 원래 틀린건데 시간초과가 났다.. 이거죠?

bupjae   5년 전

네. 


작성한 코드는 원래 틀린 코드입니다만, 1번 코드는 15~19번째 줄에서 문제에서 주어진 시간보다 더 많이 잡아먹었기 때문에 채점 프로그램은 출력 결과를 기다리지 않고 강제로 중단한 뒤 "시간 초과" 딱지를 붙이게 됩니다.

eric00513   5년 전

그럼 어떻게 시간초과를 해결할 수 있을까요?

대소문자 구분 안하고?

gallopsys   5년 전

대소문자를 구분하지 않고 문제를 푼다는 건 말도 안 되고요, 시간초과의 문제는 윗 분 말씀대로 혹은 두 번째 소스코드에 적으신대로 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라고 출력되어야 할 것이, ?라고 표시되는 것입니다.

위의 코드를 짜실 때 어떤 생각으로 짜셨는진 잘 모르겠습니다만, 알파벳 범위만큼 돌면서 최대값을 확보하신 뒤에 그 최대값과 겹치는 (그러니까 최대값이 같은) 알파벳 개수가 있으면 ?를 출력하도록 만드는 건 어떨까요?

eric00513   5년 전

@gallopsys님, 그렇게 하면 대신 시간복잡도는 O(n) 만큼 늘어나겠네요? (최악의 경우에)

eric00513   5년 전

가 아니라 에이 26번 밖에 for문이 더 도네요...

eric00513   5년 전

정말 감사합니다! 덕분에  맞았습니다!  가 나타났습니다.

eric00513   5년 전

아 맞다 특히 @gallopsys님, @bupjae님, 모두 감사합니다

댓글을 작성하려면 로그인해야 합니다.