0부터 9까지의 숫자로만 구성된 문자열이 주어지며, 이 문자열은 하나의 십진수를 나타냅니다. 우리의 목표는 값이 X보다 큰 숫자에 해당하는 모든 부분 문자열(substring)을 찾아 그 개수를 세는 것입니다. 단, 부분 문자열은 0으로 시작해서는 안 된다는 조건이 있습니다. 예를 들어 "2021"이라는 문자열에서 "02", "021", "0"처럼 앞에 0이 붙는 부분 문자열은 유효한 후보에서 제외됩니다.
해결 방법은 간단합니다. 모든 부분 문자열의 첫 번째 자릿수를 먼저 검사하여, 그 값이 0이 아니라면 해당 인덱스에서 시작하는 부분 문자열들을 만들고 stoi() 함수를 사용해 정수로 변환합니다. 변환된 값이 X보다 크면 카운트를 증가시키는 방식입니다.
입력 및 출력 예제
예시를 통해 문제를 더 자세히 이해해 보겠습니다.
입력 − str="123", X=12
출력 − X보다 큰 숫자 값을 가진 부분 문자열의 개수: 2
설명 − 12보다 큰 부분 문자열은 "123"과 "23" 두 개입니다.
입력 − str="111", X=100
출력 − X보다 큰 숫자 값을 가진 부분 문자열의 개수: 1
설명 − "111"만이 100보다 큰 값을 가집니다.
문제 해결 접근 방식
숫자로만 이루어진 문자열 str을 입력받습니다.
str의 길이를 len = str.length()로 저장합니다.
greater_X(string str, int x) 함수는 문자열과 정수 x를 매개변수로 받아, X보다 큰 십진수를 형성하는 부분 문자열의 개수를 반환합니다.
FOR 루프를 사용하여 문자열을 순회합니다.
인덱스 i=0부터 i<len까지, 왼쪽에서 오른쪽 방향으로 탐색합니다.
str[i] != '0'인 경우, 해당 위치에서 시작하는 모든 부분 문자열은 유효한 후보가 됩니다.
부분 문자열의 길이를 결정하기 위해 j=1부터 i+j<=len까지 내부 루프를 돌립니다.
str.substr(i, j)를 stoi() 함수로 십진수 정수로 변환한 뒤, 그 값이 X보다 크면 count를 증가시킵니다.
모든 탐색이 끝나면 count를 결과로 반환합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int greater_X(string str, int x){
int count = 0;
int len = str.length();
for (int i = 0; i < len; ++i){
if(str[i] != '0'){
for (int j=1; (i + j) <= len; ++j){
if (stoi(str.substr(i, j)) > x){
count++;
}
}
}
}
return count;
}
int main(){
string str = "987";
int x = 100;
cout<<"X보다 큰 숫자 값을 가진 부분 문자열의 개수: "<<greater_X(str, x);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.
X보다 큰 숫자 값을 가진 부분 문자열의 개수: 1
위 예제에서 문자열 "987"의 경우, 0으로 시작하지 않으면서 100보다 큰 값을 가지는 부분 문자열은 "987"뿐이므로 결과는 1이 됩니다.