[백준] 1152번 단어의 개수

https://www.acmicpc.net/problem/1152

1152번: 단어의 개수

1.문제 분석

  모든 단어는 공백에 의해서만 구분되고 연속된 공백(' ')도 존재하지 않으므로 공백의 개수를 구하면 된다. 다만 [그림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;
}