C++로 문자열에서 각 문자 오른쪽의 더 큰 요소 개수 구하기

문자열이 주어졌을 때, 각 문자의 오른쪽에 있는 더 큰 문자의 개수를 세는 것은 코딩 테스트에서 자주 등장하는 기본적인 문제입니다. 예시를 통해 자세히 살펴보겠습니다.

입력

string = "abc"

출력

2 1 0

'a'의 오른쪽에는 'a'보다 큰 문자가 2개('b', 'c') 있으므로 결과는 2입니다.

'b'의 오른쪽에는 'b'보다 큰 문자가 1개('c') 있으므로 결과는 1입니다.

'c'의 오른쪽에는 'c'보다 큰 문자가 없으므로 결과는 0입니다.

알고리즘

• 문자열을 초기화합니다.

• 각 문자의 개수를 저장할 배열을 초기화합니다.

• 두 개의 중첩 반복문을 사용해 문자열을 순회합니다.

  • 한 번에 한 문자씩 가져온 뒤, 그 뒤에 있는 모든 문자와 비교합니다.

  • 현재 문자가 뒤의 문자보다 작으면 해당 위치의 카운트 값을 증가시킵니다.

• 모든 문자의 개수를 출력합니다.

구현

다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
void countCharNextLargerElementsCount(string str) {
    int len = str.length(), count[len];
    for (int i = 0; i < len; i++) {
        count[i] = 0;
    }
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (str[i] < str[j]) {
                count[i]++;
            }
        }
    }
    for (int i = 0; i < len; i++) {
        cout << count[i] << " ";
    }
    cout << endl;
}
int main() {
    string str = "abcdefgh";
    countCharNextLargerElementsCount(str);
    return 0;
}

출력

위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.

7 6 5 4 3 2 1 0

복잡도 분석

위 방식은 두 개의 중첩 반복문을 사용하기 때문에 시간 복잡도는 O(n²)입니다. 여기서 n은 문자열의 길이입니다. 공간 복잡도는 각 위치의 개수를 저장하기 위해 O(n) 크기의 추가 배열이 필요합니다.

문자열이 매우 긴 경우에는 정렬된 문자 목록과 이진 탐색 또는 펜윅 트리(Fenwick Tree)를 활용하면 O(n log n)까지 성능을 개선할 수 있습니다.