C++로 해결하는 반복 문자열 문자 비교 쿼리 문제

이 문제에서는 문자열 str과 두 개의 값 a, b로 이루어진 Q개의 쿼리가 주어집니다. 우리가 작성해야 할 프로그램은 C++을 사용하여 반복되는 문자열 안에서 주어진 위치의 문자들을 비교하는 쿼리를 처리하는 것입니다.

문제 설명

각 쿼리를 처리할 때마다 인덱스 a와 인덱스 b에 위치한 문자가 서로 같은지 확인하고, 그 결과에 따라 적절한 값을 반환해야 합니다.

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

입력: str = "tutorialspoint"
Q = 2
쿼리 = {{0, 2}, {4, 7}}

출력:
Repeated(반복됨)
Not Repeated(반복되지 않음)

풀이 설명

쿼리 1의 경우, 인덱스 0에 있는 문자는 't'이고 인덱스 2에 있는 문자 역시 't'입니다. 따라서 두 문자는 서로 같습니다.

쿼리 2의 경우, 인덱스 4에 있는 문자는 'r'이고 인덱스 7에 있는 문자는 'l'입니다. 따라서 두 문자는 서로 다릅니다.

해결 접근 방법

이 문제는 인덱스 a와 b에 해당하는 문자가 동일한지만 확인하면 되는 비교적 간단한 문제입니다. 여기서 핵심은 문자열이 반복된다는 점입니다. 주어진 인덱스가 문자열 길이보다 크다면 나머지 연산(index % len)을 통해 한 주기 안에서의 실제 문자 위치를 구할 수 있습니다. 예를 들어 문자열의 길이가 14일 때 인덱스 32의 문자는 인덱스 32 % 14 = 4에 있는 문자와 동일합니다. 이러한 성질 덕분에 아무리 큰 인덱스가 입력되더라도 O(1) 시간 복잡도로 해당 문자를 찾아 비교할 수 있습니다.

예제 코드

#include <iostream>
#include <string>
using namespace std;
bool isrepeated(string str, int len, int a, int b){
    if(a > len)
        a %= len;
    if(b > len)
        b %= len;
    if(str[a] == str[b])
        return true;
    else
        return false;
}
int main(){
    string str = "tutorialspoint";
    int len = str.length();
    int Q = 3;
    int query[Q][2] = {{0, 2}, {3, 32}, {5, 18}};
    for(int i = 0; i < Q; i++){
        if(isrepeated(str, len, query[i][0], query[i][1]))
            cout<<"Character is repeated in both the index values"<<endl;
        else
            cout<<"Character is not repeated in both the index values"<<endl;
    }
    return 0;
}

출력 결과

Character is repeated in both the index values
Character is not repeated in both the index values
Character is not repeated in both the index values

코드 설명

isrepeated() 함수는 문자열, 문자열의 길이, 비교할 두 인덱스 a와 b를 매개변수로 받습니다. 각 인덱스가 문자열 길이보다 크면 나머지 연산을 통해 유효한 범위의 인덱스로 변환한 뒤, 두 위치의 문자를 비교하여 같으면 true, 다르면 false를 반환합니다.

main() 함수에서는 길이가 14인 문자열 "tutorialspoint"에 대해 세 개의 쿼리 {0, 2}, {3, 32}, {5, 18}를 순차적으로 처리합니다. 첫 번째 쿼리에서는 인덱스 0과 2의 문자 't'가 서로 같아 반복됨(repeated)으로 판정되며, 나머지 두 쿼리는 나머지 연산 후에도 문자가 서로 달라 반복되지 않음(not repeated)으로 출력됩니다.