알파벳으로 구성된 문자열이 주어졌을 때, 문자열 안에는 동일한 문자가 최소 두 번 이상 등장할 수 있습니다. 이 문제의 목표는 같은 문자가 등장하는 임의의 두 위치 사이에 존재하는 문자 수의 최댓값을 구하는 것입니다. 만약 문자열에 중복된 문자가 전혀 없다면 -1을 반환해야 합니다.
문제 예시
예제 1
입력 − str = "abcdba"
출력 − 문자열에서 같은 두 문자 사이의 최대 문자 수 : 4
설명 − 반복되는 문자는 'a'와 'b'이며 각 인덱스는 다음과 같습니다.
1. 'a' : 첫 번째 인덱스 0, 마지막 인덱스 5 → 사이 문자 수 = 5 - 0 - 1 = 4 2. 'b' : 첫 번째 인덱스 1, 마지막 인덱스 4 → 사이 문자 수 = 4 - 1 - 1 = 2 반복되는 알파벳 사이의 최대 문자 수 : 4
예제 2
입력 − str = "AbcAaBcbC"
출력 − 문자열에서 같은 두 문자 사이의 최대 문자 수 : 5
설명 − 반복되는 문자는 'A', 'b', 'c'이며 각 인덱스는 다음과 같습니다.
1. 'A' : 첫 번째 인덱스 0, 마지막 인덱스 3 → 사이 문자 수 = 3 - 0 - 1 = 2 2. 'b' : 첫 번째 인덱스 1, 마지막 인덱스 7 → 사이 문자 수 = 7 - 1 - 1 = 5 3. 'c' : 첫 번째 인덱스 2, 마지막 인덱스 6 → 사이 문자 수 = 6 - 2 - 1 = 3 반복되는 알파벳 사이의 최대 문자 수 : 5
참고 − 입력 문자열이 "abcdefg"처럼 중복된 문자가 하나도 없다면 함수는 -1을 반환합니다.
프로그램에서 사용하는 접근 방식
- 문자열을 담고 있는 문자 배열 Str[]을 사용합니다.
- maxChars(char str[], int n) 함수는 반복되는 두 알파벳 사이의 최대 문자 수를 계산합니다.
- 변수 maxC를 -1로 초기화합니다.
- 바깥쪽 for 루프에서 문자열 배열을 처음부터 끝까지 순회합니다.
- 안쪽(중첩) for 루프에서 나머지 문자들을 탐색하며 중복 여부를 검사합니다. (if (str[i] == str[j]))
- 중복이 발견되면 두 인덱스의 차이를 이용해 사이 문자 수를 계산합니다. (temp = j - i - 1)
- 이 값이 지금까지 찾은 최댓값보다 크다면 maxC에 저장합니다.
- 전체 문자열을 모두 순회한 후 maxC를 반환합니다.
예제 코드
#include <stdio.h>
#include <math.h>
int maxChars(char str[], int n){
int size = n;
int maxC = -1;
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (str[i] == str[j]){
int temp = abs(j - i - 1);
maxC = maxC > temp ? maxC : temp;
}
return maxC;
}
// Driver code
int main(){
char Str[] = "AbcAaBcbC";
printf("Maximum number of characters between any two same character in a string : %d",
maxChars(Str, 9));
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Maximum number of characters between any two same character in a string : 5
복잡도 분석
위 방법은 두 개의 중첩 루프를 사용하여 모든 문자 쌍을 비교하므로 시간 복잡도는 O(n²)입니다. 추가적인 배열 없이 상수 변수만 사용하기 때문에 공간 복잡도는 O(1)입니다.