인프런 커뮤니티 질문&답변

dkswhdgur1209님의 프로필 이미지

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

1-K

1 - K의 cnt[]배열크기 질문합니다

23.03.08 17:31 작성

·

471

0

안녕하세요 강사님!

1 - K 문제에서 cnt배열의 크기를 200으로 설정하셨는데 200인 이유가 무엇인가요?

답변 4

2

큰돌님의 프로필 이미지
큰돌
지식공유자

2023. 03. 10. 05:15

안녕하세요 1209님 ㅎㅎ

1 - K 문제에서 cnt배열의 크기를 200으로 설정하셨는데 200인 이유가 무엇인가요?

>> 26이상만 잡으시면 됩니다. 저는 그냥 좀 더 크게 잡았습니다.

 

char형 a가 최대크기가 50인 문자열s 순회하여 문자열 s에 있는 알파벳마다(char형) cnt[a]의 값이 1씩 증가하기 때문에 cnt[26]이 아닌가요..?

>> 네 맞습니다. 딱 맞게 그렇게 잡아도 됩니다.

 

1-B와는 달리 cnt[]의 크기가 200인 이유가 궁금합니다.

>> 보통은 필요한 배열크기 + 4 만큼 잡는게 좋습니다. 그래서 보통은 26이 필요하다면 30으로 잡는게 좋지만 저거 같은 경우는 그냥 크게 200 잡은거에요 ㅎㅎ 별다른 이유는 없습니다.

 

감사합니다.

 

 

0

dkswhdgur1209님의 프로필 이미지
dkswhdgur1209
질문자

2023. 03. 17. 14:35

http://boj.kr/06440aeccbb045b8829d9cdadf5f6a33

이 링크는 답지 12행에 있는 if(cnt[i])가 아니라 while(cnt[i)로 바꾸고 이에 맞춰, 18-20행을 바꿔보았습니다.

제출하게되면, 시간초과가 나는데 while을 이용한 제 코드의 시간복잡도는 얼마인가요..?

0

dkswhdgur1209님의 프로필 이미지
dkswhdgur1209
질문자

2023. 03. 17. 14:12

http://boj.kr/1cb106485f6b478ab640c60a6dda5cc0

배열크기를 26, 30으로 잡고했더니 시간초과가 뜹니다.

배열크기를 60, 70으로 설정하면 메모리 초과로 뜹니다.

배열크기를 100으로 해야 정답입니다 라고 뜹니다.

이럴 경우 배열의 크기가 26이 아닌것 같아서 배열크기를 어떻게 설정 해야하는지 재 질문 드립니다.

0

dkswhdgur1209님의 프로필 이미지
dkswhdgur1209
질문자

2023. 03. 08. 17:42

+++본문과 덧붙입니다.

char형 a가 최대크기가 50인 문자열s 순회하여 문자열 s에 있는 알파벳마다(char형) cnt[a]의 값이 1씩 증가하기 때문에 cnt[26]이 아닌가요..?

1 - B에서 알파벳 개수를 구할 때, for(char a : str) {cnt[a - 'a']++;} 에서는 char형 a가 str을 순회하며 str의 범위는 a-z까지이므로 cnt크기가 26인것을 알 수 있었습니다.

1-B와는 달리 cnt[]의 크기가 200인 이유가 궁금합니다.