C++로 문자열의 세그먼트 개수 구하는 방법

문제 개요

문자열 s가 주어졌을 때, 이 문자열에 포함된 세그먼트(segment)의 개수를 구하는 것이 목표입니다. 여기서 세그먼트란 공백을 포함하지 않는 연속된 문자들의 묶음을 의미합니다.

예를 들어, 입력 문자열이 "Hello, I love programming"이라면 세그먼트가 총 4개이므로 출력값은 4가 됩니다.

해결 접근 방법

이 문제는 문자열을 한 번만 순회하면 해결할 수 있습니다. 알고리즘의 동작 과정은 다음과 같습니다.

1. 세그먼트 개수를 저장할 변수 n을 0으로 초기화합니다.
2. i를 0으로 초기화하고, i가 문자열 길이보다 작은 동안 다음을 반복합니다.
   • s[i]가 공백이 아니라면 새로운 세그먼트가 시작된 것이므로 n을 1 증가시킵니다.
   • 이어서 i가 문자열 길이 미만이고 s[i]가 공백이 아닌 동안 i를 계속 증가시켜, 현재 세그먼트가 끝나는 지점까지 이동합니다.
3. 반복이 종료되면 n을 반환합니다. 이 방식은 각 세그먼트의 시작 지점에서만 카운트하므로, 연속된 공백이 여러 개 있어도 정확하게 동작합니다.

구현 예시

아래의 C++ 코드를 통해 구현 방법을 더 자세히 이해할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int countSegments(string s) {
      int n = 0;
      for(int i = 0; i < s.size(); i++){
         if(s[i] != ' ')
            n++;
         while( i < s.size() && s[i] != ' ')
            i++;
      }
      return n;
   }
};
main(){
   Solution ob;
   cout << (ob.countSegments("Hello, I love programming"));
}

입력

"Hello, I love programming"

출력

4

복잡도 분석

시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이로, 문자열을 한 번만 순회하기 때문입니다. 공간 복잡도는 추가 변수만 사용하므로 O(1)입니다.