C++에서 두 대문자 사이의 고유한 소문자 알파벳 최대 개수 구하기

이 문제는 주어진 문자열에서 두 대문자 사이에 존재하는 서로 다른(고유한) 소문자 알파벳의 최대 개수를 찾는 것입니다.

예시를 통해 문제를 자세히 이해해 보겠습니다.

입력 예시 1

str = "JKyubDoorG"

출력

설명

대문자 K와 D 사이에는 "yub"라는 소문자 3개가 존재하므로 개수는 3이 됩니다.

또한 대문자 D와 G 사이에는 "oor"이 존재하지만, 'o'가 중복된 문자이기 때문에 고유한 문자만 세면 2가 됩니다.

따라서 최종 출력은 3입니다.

입력 예시 2

str = "ABcefsTaRpaep"

출력

풀이 접근 방법

Max() 함수 안에서 int size = s.length()를 선언하여 주어진 문자열의 길이를 저장합니다.
i = 0부터 size 미만까지 반복하면서 s[i] >= 'A' && s[i] <= 'Z' 조건으로 첫 번째 대문자를 찾습니다. 대문자를 발견하면 인덱스를 하나 증가시킨 뒤 반복문을 종료하여, 문자열 맨 앞에 있는 소문자들은 계산에서 제외합니다.
최종 답을 저장할 int ans = 0과, 알파벳별 등장 여부를 기록할 배열 cnt[26] = {0}을 초기화합니다.
다시 i = 0부터 size 미만까지 반복하면서 현재 문자가 대문자인지 확인합니다. 대문자라면 현재 구간의 최댓값을 저장할 int CurrMax = 0을 초기화합니다.
인덱스 0부터 25까지 반복하면서 cnt[i] > 0인 경우 CurrMax를 증가시켜, 직전 대문자 이후 등장한 고유 소문자의 개수를 셉니다.
반복문이 끝나면 ans = max(ans, CurrMax)로 정답을 갱신하고, memset(cnt, 0, sizeof(cnt))를 사용해 cnt 배열을 초기화하여 다음 구간을 위한 준비를 합니다.
현재 문자가 소문자(s[i] >= 'a' && s[i] <= 'z')라면 cnt[s[i] - 'a']++로 해당 알파벳의 등장 횟수를 증가시킵니다.
모든 반복이 끝나면 ans를 반환합니다.

구현 코드

#include <bits/stdc++.h>
using namespace std;
int Max(string s){
   int size = s.length();
   // 문자열 앞부분의 소문자는 무시
   for (int i = 0; i < size; i++){
      if (s[i] >= 'A' && s[i] <= 'Z'){
         i++;
         break;
      }
   }
   int ans = 0;
   int cnt[26] = { 0 };
   for (int i = 0; i < size; i++) {
      // 알파벳이 대문자인 경우
      if (s[i] >= 'A' && s[i] <= 'Z'){
         // 지금까지 등장한
         // 고유 소문자 개수 계산
         int CurrMax = 0;
         for (int i = 0; i < 26; i++){
            if (cnt[i] > 0)
               CurrMax++;
         }
         // 정답 갱신
         ans = max(ans, CurrMax);
         // 카운트 배열 초기화
         memset(cnt, 0, sizeof(cnt));
      }
      // 알파벳이 소문자인 경우
      if (s[i] >= 'a' && s[i] <= 'z')
         cnt[s[i] - 'a']++;
   }
   return ans;
}
// 드라이버 함수
int main(){
   string str = "JKyubDoorG";
   cout << Max(str);
   return 0;
}

실행 결과

시간 복잡도

문자열을 한 번 순회하고, 대문자를 만날 때마다 크기 26의 카운트 배열만 확인하므로 전체 시간 복잡도는 O(n)입니다. 여기서 n은 문자열의 길이입니다. 공간 복잡도 역시 크기 26의 배열만 사용하므로 O(1)로 상수 공간 내에서 해결됩니다.