[문제]
영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 단, 한 단어가 여러 번 등장하면 등장한 횟수만큼 모두 세어야 한다.
[입력]
첫 줄에 영어 대소문자와 공백으로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 공백 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열은 공백으로 시작하거나 끝날 수 있다.
[출력]
첫째 줄에 단어의 개수를 출력한다.
[풀이]
생각 보다 쉽지 않았던 문제여서 이렇게 기록해보려고 한다.
https://www.acmicpc.net/board/view/30509
일단 해당 게시물에서 힌트를 얻었다.
다른 알파벳들의 값을 어떻게 담을지 생각하던 도중 배열의 index를 알파벳의 ascii로
각 index에 있는 값은 해당 알파벳의 개수로하였다.
#include <iostream>
int const Length = 1000001;
int cnt[26];전역 변수는 선언과 동시에 지역 변수와 달리 쓰레기 값이 아닌 0으로 초기화가 되는데 배열도 마찬가지이다.
따라서 이를 이용하여 카운트에 사용될 int 배열을 선언.
문자열의 길이 또한 함수에서 지역 변수의 문자열을 초기화하기위해 선언하였다.
또한 문자열의 끝을 표시하기 위해서 '\0'이 포함되므로 이를 고려하여 한 자리를 추가 생산해야한다.
#include <iostream>
int const Length = 1000001;
int cnt[26];
int main()
{
//char str[1000001] 런타임 에러 작은 스택에 많은 배열 선언 때문
char* str = (char*)malloc(sizeof(char) * Length);//때문에 배열을 자유저장소에 할당
int index = 0;//첫 Loop에서 str을 읽을 때 사용할 index
int current;//첫 Loop 현재 문자
bool isSame = false;
int result;//최종 출력용
int currentMax = 0;//두번째 Loop에서 가장 큰 값 cashing
scanf("%s", str);
if(str != NULL)
while (str[index] != NULL)
{
str[index] = toupper(str[index]);//출력이 모두 대문자여야하며 원활한 대소문자의 비교를 위해서 대문자로 전환
current = str[index] - (int)'A';
cnt[current] += 1;
index += 1;
}
for (int i = 0; i < sizeof(cnt) / sizeof(int); i++)
{
if (currentMax < cnt[i])
{//현재 알파벳의 수가 가장 수가 많은 알파벳 보다 많다면
isSame = false;
result = i;
currentMax = cnt[i];
}
else if (currentMax == cnt[i]) isSame = true;//만약 같다면
}
if (isSame) printf("?");
else printf("%c", (char)(result + 'A'));
return 0;
}
0(n^2)의 복잡도를 갖는 로직은 시간을 초과하게 된다.
따라서 알파벳을 세는 루프와 가장 큰 수를 찾는 루프를 나눴다.(원래 이중 루프였다)