C++로 텍스트의 볼륨 계산하기: 단어별 대문자 개수의 최댓값 구현

문제 설명

n개의 문자로 이루어진 문자열 S가 있다고 가정해 보겠습니다. S는 영어 대소문자로만 구성된 단어들이 공백 하나로 구분되어 있는 형태입니다. 여기서 단어의 볼륨(volume)은 해당 단어에 포함된 대문자의 개수를 의미하며, 텍스트 전체의 볼륨은 모든 단어 중에서 가장 큰 볼륨 값입니다. 즉, 우리가 구해야 할 답은 주어진 텍스트의 볼륨입니다.

예를 들어 "Paper MILL"이라는 문장을 보면, "Paper"의 볼륨은 1(P), "MILL"의 볼륨은 4(M, I, L, L)이므로 텍스트 전체의 볼륨은 4가 됩니다.

풀이 접근 방법

이 문제는 문자열을 한 글자씩 순회하면서 아래 규칙대로 처리하면 간단하게 해결할 수 있습니다.

• 지금까지 찾은 최대 볼륨을 저장할 변수 ans와, 현재 단어의 대문자 개수를 셀 변수 a를 0으로 초기화합니다.
• 현재 문자가 'A'부터 'Z' 사이에 속하면 a를 1 증가시킵니다.
• 공백 문자를 만나면 직전 단어의 볼륨(a)과 ans를 비교해 더 큰 값을 ans에 저장한 뒤, a를 0으로 초기화하여 다음 단어를 준비합니다.
• 반복문이 끝난 후 마지막 단어의 볼륨도 한 번 더 비교해 줍니다. 마지막 단어 뒤에는 공백이 없기 때문입니다.

위 과정을 의사코드로 나타내면 다음과 같습니다.

ans := 0
a := 0
n := size of S
for initialize i := 0, when i <= n, update (increase i by 1), do:
    s := S[i]
    if s >= 'A' and s <= 'Z', then:
        (increase a by 1)
    if s is same as blank space, then:
        ans := maximum of ans and a
        a := 0
ans := maximum of ans and a
return ans

C++ 구현 예제

더 확실한 이해를 위해 실제 C++ 코드로 구현한 예제를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
int solve(string S){
    int ans = 0, a = 0;
    int n = S.size();
    for (int i = 0; i <= n; i++){
        char s = S[i];
        if ((s >= 'A') && (s <= 'Z'))
            a++;
        if (s == ' '){
            ans = max(ans, a);
            a = 0;
        }
    }
    ans = max(ans, a);
    return ans;
}
int main(){
    string S = "Paper MILL";
    cout << solve(S) << endl;
}

실행 결과

입력

"Paper MILL"

출력

4

핵심 정리

이 알고리즘은 문자열을 한 번만 순회하면 되기 때문에 시간 복잡도는 O(n), 추가 메모리 사용은 상수 수준이므로 공간 복잡도는 O(1)입니다. 반복문을 i <= n까지 돌리고 종료 후 마지막 카운트를 한 번 더 비교하는 것이, 공백으로 끝나지 않는 일반적인 문장에서도 마지막 단어를 놓치지 않는 핵심 포인트입니다.