slowbooktech   2년 전

안녕하세요, 최다 반복 문자 출력코드 질문 드립니다.

[배경]

분명 정상작동하는 코드입니다. 예제의 모든 값과 동일하게 나오고, 본 게시판의 질문 검색을 통해 확인한 예시들 (aabbcc, Aabbcc, z)도 정상적으로 출력되었습니다. 

[문제상황]

채점 시 시간초과가 발생합니다.

오류로는, 비주얼스튜디오 경고메시지 'arr에서 잘못된 데이터를 읽고 있습니다. 읽기 가능한 크기는 104바이트인데 실제로 128바이트를 읽고 있습니다.' 가 발생합니다.

오류나는 부분
else{
   arr[input[i] - 65]++;
}

[질문 1]

채점 시 시간초과가 뜨는 이유가 무엇일까요? 오류나는 부분 때문인가요?

[질문 2]

그렇다면, if 문(arr[input[i] - 97]++;)에서 뜨지 않는 오류가 else문에서 발생하는 이유가 무엇인가요?

두 질문중 하나만 답해주셔도 진심으로 감사드립니다.

kth   2년 전

문제를 읽어보진 않았지만 추측해서 답변드립니다.

1.

아뇨. 1번은 strlen(input) 함수 때문입니다. strlen함수는 문자배열의 길이를 계산하기 위해 O(n)만큼 시간복잡도가 나옵니다.

for문이 n번 돌고 strlen(input)을 계산하기 위해 n번 더 돌아서 총 n^2의 시간이 들어서 시간초과라고 파악됩니다.


2.

경고메시지라 오류는 아니라고 생각됩니다.

저도 정확하게는 잘모르지만 아는만큼 설명해 보겠습니다.

int배열이므로 byte 수로 나누면

104 / 4 = 26 바이트 => arr 선언한 바이트, 즉 arr[26]: arr[0]~ arr[25] 까지 읽어야 하는데,

128 / 4 = 32 바이트 => arr[32]: arr[0]~arr[31] 까지 읽어버린다.

첫번 째 input[i] > 96에서 거르고 남는 범위는

0 <= input[i] <= 96 입니다.


여기서 input[i]가 'A'(65) ~ 'z'(90) 이외의 값들 중에 경고 메시지로 인식되는 것 같습니다.

96값이 'z'(90) 보다 6바이트 더 크므로 저 경고로 인식되는 것으로 추정되네요.

컴파일러는 input[i]가 어떤 범위를 가지지 모르기 때문에 조금 더 명확하게 범위를 가져주면 될 것 같습니다.


이상입니다.

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