C++로 주어진 문자열의 부분 문자열에서 반복되지 않는 마지막 문자를 찾는 쿼리 구현하기

이 문제에서는 문자열 str과 각각 두 개의 정수로 구성된 Q개의 쿼리가 주어집니다. 우리의 과제는 C++에서 주어진 문자열의 부분 문자열 내에서 반복되지 않는 마지막 문자를 찾는 쿼리를 처리하는 프로그램을 작성하는 것입니다.

문제 설명

각 쿼리에는 두 개의 정수 L과 R이 주어집니다. 쿼리를 해결하기 위해 인덱스 L부터 R까지의 부분 문자열을 추출한 뒤, 해당 부분 문자열 안에서 단 한 번만 등장하는(즉, 반복되지 않는) 마지막 문자를 찾아야 합니다.

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

입력: str = "Tutorialspoint", Q = 2

query = {{4, 8}, {2, 6}}

출력: s , a

설명

subStr[4...8] = "rials". 이 부분 문자열에서 반복되지 않는 마지막 문자는 's'입니다. 모든 문자의 빈도수가 1이므로 가장 뒤에 있는 문자인 's'가 정답이 됩니다.

subStr[2...6] = "toria". 이 부분 문자열에서 반복되지 않는 마지막 문자는 'a'입니다. 역시 모든 문자가 한 번씩만 등장하므로 마지막 문자인 'a'가 결과입니다.

해결 접근 방식

이 문제를 해결하려면 한 번만 등장하는 문자를 찾아야 합니다. 이를 위한 간단하고 효율적인 방법은 charFreq[][]라는 2차원 배열(매트릭스)을 만들어 각 위치까지의 문자별 누적 빈도수를 미리 계산해 두는 것입니다. 이렇게 하면 각 쿼리마다 부분 문자열을 직접 순회하지 않고도, 특정 구간 [L, R] 내에서 각 문자의 등장 횟수를 O(1) 시간에 구할 수 있습니다. 쿼리를 처리할 때는 모든 문자의 빈도수를 확인하여 빈도수가 1인 마지막 문자를 반환하면 됩니다. 만약 그런 문자가 없다면 -1을 반환합니다.

알고리즘

1. 문자열을 순회하며 각 인덱스 i까지의 256개 ASCII 문자별 누적 빈도수를 charFreq 배열에 저장합니다.
2. 각 쿼리 (L, R)에 대해, 문자열의 끝(R)부터 시작(L)까지 거꾸로 순회합니다.
3. 현재 문자 ch에 대해 charFreq[ch][R] - charFreq[ch][L-1] 값이 1이라면 해당 문자가 구간 내에서 한 번만 등장한 것이므로 즉시 반환합니다.
4. 끝까지 찾지 못했다면 "-1"을 반환합니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
int charFreq[256][1000] = {0};
void initialiseCharFrequency(string str, int n) {
   charFreq[(int)str[0]][0] = 1;
   for (int i = 1; i < n; i++) {
      char ch = str[i];
      for (int j = 0; j < 256; j++) {
         char charToUpdate = (char)j;
         if (charToUpdate == ch)
            charFreq[j][i] = charFreq[j][i - 1] + 1;
         else
            charFreq[j][i] = charFreq[j][i - 1];
      }
   }
}
string returnCharFromString(char x) {
   string s(1, x);
   return s;
}
string lastUniqueChar(string str, int n, int start, int end) {
   for (int i = end; i >= start; i--) {
      char ch = str[i];
   if ((charFreq[(int)ch][end] - charFreq[(int)ch][start - 1]) ==1)
      return returnCharFromString(ch);
   }
   return "-1";
}
int main() {
   string str = "TutorialsPoint";
   int len = str.length();
   int Q = 3;
   int query[Q][2] = { { 2, 9 }, { 2, 3 }, { 0, 12 } };
   initialiseCharFrequency(str, len);
   for (int i = 0; i < Q; i++)
      cout<<"\nFor Query "<<(i+1)<<": The last non-repeating character in the sub-string of a given string is "<<lastUniqueChar(str, len,query[i][0], query[i][1]);
}

출력 결과

For Query 1: The last non-repeating character in the sub-string of a given string is P
For Query 2: The last non-repeating character in the sub-string of a given string is o
For Query 3: The last non-repeating character in the sub-string of a given string is n

코드 설명

initialiseCharFrequency 함수는 전처리 단계로, 문자열의 각 위치까지 어떤 문자가 몇 번 등장했는지를 charFreq 배열에 누적 저장합니다. 이 덕분에 이후 쿼리에서 구간별 문자 빈도를 빠르게 계산할 수 있습니다.

lastUniqueChar 함수는 주어진 구간 [start, end]를 뒤에서부터 앞으로 순회하면서, charFreq의 누적값 차이를 이용해 해당 문자가 구간 내에서 정확히 한 번만 등장했는지 확인합니다. 조건을 만족하는 첫 번째(즉, 가장 뒤에 있는) 문자를 즉시 반환하므로 효율적입니다.

위 실행 결과에서 첫 번째 쿼리 {2, 9}의 경우 부분 문자열은 "torialsPoi"이며, 이 중 한 번만 등장하는 마지막 문자는 'P'입니다. 두 번째 쿼리 {2, 3}의 부분 문자열 "to"에서는 'o'가, 세 번째 쿼리 {0, 12}의 부분 문자열 "TutorialsPoin"에서는 'n'이 반복되지 않는 마지막 문자로 출력됩니다.

시간 복잡도 분석

전처리 단계는 O(N × 256)의 시간이 소요되며, 각 쿼리는 최악의 경우 O(K) 시간이 걸립니다(여기서 K는 구간 길이). 다만 빈도수 조회 자체는 O(1)이므로, 쿼리가 많은 상황에서도 매우 효율적으로 동작합니다. 공간 복잡도는 O(256 × N)으로, 문자 종류가 제한적인 경우 실용적으로 사용할 수 있습니다.