문제 개요
문자열 str, 한 개의 문자, 그리고 양의 정수 N이 주어졌다고 가정해 봅시다. 이때 문자열 str은 무한히 반복된다고 하며, 우리가 구해야 할 값은 반복되는 문자열의 처음 N개 문자 안에서 주어진 문자가 총 몇 번 등장하는지입니다.
예를 들어 str이 "abac"이고, 찾으려는 문자가 'b', N이 10이라고 해보겠습니다. "abacabacabac…"에서 처음 10개 문자에는 'b'가 두 번 등장합니다.
참고 − str과 문자 ch는 서로 같은 대소문자 체계(모두 대문자 또는 모두 소문자)로 주어진다고 가정합니다.
예제로 이해하기
입력
str = "TPTTTT" ch = 'T' n = 12
출력
Count of occurrences of a character in a repeated string are: 10
설명
str에 포함된 'T'의 개수는 5개이고, str의 길이는 6입니다. n=12일 때 str은 정확히 두 번 완전히 반복되므로 'T'의 총 등장 횟수는 5×2=10이 됩니다.
입력
str = "sets" ch = 's' n = 15
출력
Count of occurrences of a character in a repeated string are: 7
설명
str 속 's'의 개수는 2개이고, str의 길이는 4입니다. n=15일 때 str은 처음 12자에서 세 번 완전히 반복되므로 이 구간에서 's'는 3×2=6번 등장합니다. 남은 3글자("set")에서는 's'가 한 번 더 나타나므로 최종 개수는 6+1=7이 됩니다.
접근 방법
이 문제는 다음 순서로 효율적으로 해결할 수 있습니다. 먼저 str 안에서 문자 ch가 등장하는 횟수를 셉니다. 그다음 N을 str의 길이로 나누어 str이 완전히 몇 번 반복되는지(N ÷ str 길이)를 구합니다. 완전한 반복 구간에서 ch의 등장 횟수는 단순 곱셈으로 계산할 수 있습니다. 마지막으로 나머지 문자(N % str 길이)만큼 str의 앞부분을 다시 확인하여 ch가 등장하면 개수에 더해주면 됩니다.
- 문자열 str을 입력받습니다.
- n은 정수, ch는 문자, str의 길이는 정수 변수로 저장합니다.
- 함수
occurrences_char(string str, int length, int n, char ch)는 str, ch, n, str의 길이를 인자로 받아 반복 문자열의 처음 n개 문자에서 ch가 등장하는 횟수를 반환합니다. - 초기 count 값을 0으로 설정합니다.
- for 루프를 사용해 str에서 ch의 등장 횟수를 셉니다. str[i] == ch인 경우마다 count를 증가시킵니다.
- n 범위 내에서 str이 반복되는 횟수는 occ = n / length로 구합니다.
- 완전한 반복 구간에서 ch의 등장 횟수는 count × occ입니다.
- 나머지 n % length개 문자에 대해서도 str[i] == ch인지 검사하여 해당하면 count를 증가시킵니다.
- 최종 count를 결과로 반환합니다.
이 방식은 문자열을 실제로 N길이만큼 늘려 확인하지 않고도 답을 구할 수 있어, 시간 복잡도가 str의 길이에 비례하는 O(L) 수준으로 매우 효율적입니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
int occurrences_char(string str, int length, int n, char ch){
int count = 0;
for (int i = 0; i < length; i++){
if (str[i] == ch){
count++;
}
}
int occ = n / length;
count = count * occ;
for (int i = 0; i < n % length; i++){
if (str[i] == ch){
count++;
}
}
return count;
}
int main(){
string str = "TPTTTT";
char ch = 'T';
int n = 12;
int length = str.size();
cout<<"Count of occurrences of a character in a repeated string are: "<<occurrences_char(str, length, n, ch);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Count of occurrences of a character in a repeated string are − 10