https://www.acmicpc.net/problem/1152
1152번: 단어의 개수
첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한
www.acmicpc.net
1.문제 분석
모든 단어는 공백에 의해서만 구분되고 연속된 공백(' ')도 존재하지 않으므로 공백의 개수를 구하면 된다. 다만 [그림1]과 같이 공백이 문자열 앞뒤에 모두 존재하면 개수에서 1을 빼고, 문자열 앞뒤에 모두 존재하지 않으면 개수에 1을 더하는 것만 고려해 주면 된다.
시간복잡도 계산
문자열의 최대 길이는 1,000,000이고 공백의 개수를 구하기 위해 문자열 길이만큼 문자비교연산을 진행한다. 따라서 최대 시간복잡도는 아래와 같다.
시간복잡도 = O(1,000,000)
2. 코드
#include<iostream>
using namespace std;
#define MAX_STRING_LENGTH 1000000
int main() {
char* str = new char[MAX_STRING_LENGTH + 1];
cin.getline(str, MAX_STRING_LENGTH + 1); // ' '포함된 문자열을 받기 위해 사용하는 함수
int wordCount = 0;
int idx;
for (idx = 0; str[idx] != '\0'; idx++)
if (str[idx] == ' ')
wordCount++;
if (str[0] != ' ' && str[idx - 1] != ' ')
wordCount++;
else if (str[0] == ' ' && str[idx - 1] == ' ')
wordCount--;
cout << wordCount << endl;
delete[] str;
return 0;
}
'개발하고 > 코딩테스트' 카테고리의 다른 글
[백준] 2839번 설탕 배달 (0) | 2023.07.15 |
---|---|
[백준] 2884번 알람 시계 (0) | 2023.07.15 |
[백준] 1006번 제곱ㄴㄴ수 (0) | 2021.08.13 |
[백준] 1008번 A/B (0) | 2021.08.02 |
[백준] 1003번 피보나치 함수 (0) | 2021.08.02 |