문제 소개
이 문제에서는 숫자로 해석할 수 있는 문자열이 하나 주어집니다. 우리가 해야 할 일은 이 문자열을 두 부분으로 나누는 것입니다. 단, 첫 번째 부분은 정수 A로 나누어 떨어져야 하고, 두 번째 부분은 정수 B로 나누어 떨어져야 합니다.
예를 들어 다음과 같습니다.
입력 : str = "123", a = 12, b = 3 출력 : YES 12 3 "12"는 a(12)로 나누어 떨어지고, "3"은 b(3)로 나누어 떨어집니다. 입력 : str = "1200", a = 4, b = 3 출력 : YES 12 00 입력 : str = "125", a = 12, b = 3 출력 : NO
이 문제에서는 사전 계산(precomputation)을 활용하여 프로그램의 실행 속도를 높이고, 더 큰 입력 제약 조건에서도 원활하게 동작하도록 만들 것입니다.
해결 접근 방법
이 접근 방식에서는 문자열을 대상으로 두 개의 루프를 실행합니다. 첫 번째 루프는 앞에서 뒤로 진행하고, 두 번째 루프는 뒤에서 앞으로 진행합니다. 그런 다음 매 지점마다 첫 번째 루프에서는 지금까지 형성된 수를 a로 나눈 나머지를, 두 번째 루프에서는 b로 나눈 나머지를 구합니다. 이렇게 하면 원하는 답을 찾을 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
void divisionOfString(string &str, int a, int b){
int n = str.length();
vector<int> mod_a(n+1, 0); // a에 대한 나머지를 저장할 배열
mod_a[0] = (str[0] - '0')%a;
for (int i=1; i<n; i++) // a에 대한 나머지를 계산하는 앞쪽 루프
mod_a[i] = ((mod_a[i-1]*10)%a + (str[i]-'0'))%a;
vector<int> mod_b(n+1, 0);
mod_b[n-1] = (str[n-1] - '0')%b;
int power10 = 10; // 마지막 인덱스에 값을 할당했으므로 10부터 시작
for (int i= n-2; i>=0; i--){ // b에 대한 나머지를 계산하는 뒤쪽 루프
mod_b[i] = (mod_b[i+1] + (str[i]-'0')*power10)%b;
power10 = (power10 * 10) % b;
}
for (int i=0; i<n-1; i++){ // 분할 지점 찾기
if (mod_a[i] != 0) // mod_a가 0이 아닌 위치는 건너뛴다
continue;
if (mod_b[i+1] == 0){ // mod_b의 다음 인덱스도 0이라면 그곳이 분할 지점
cout << "YES\n";
/*******형성된 분할 결과 출력*******/
for (int k=0; k<=i; k++)
cout << str[k];
cout << " ";
for (int k=i+1; k < n; k++)
cout << str[k];
return;
}
}
cout << "NO\n"; // 그 외에는 NO 출력
}
// 드라이버 코드
int main(){
string str = "123"; // 주어진 문자열
int a = 12, b = 3;
divisionOfString(str, a, b);
return 0;
}실행 결과
YES 12 3
코드 설명
이 접근 방식에서는 가능한 모든 분할 지점에서 형성되는 수의 나머지를 미리 계산해 두었습니다. 첫 번째 부분은 a로 나누어 떨어져야 하므로 앞쪽 루프를 돌며 해당 수를 a로 나눈 나머지를 저장하고, 두 번째 부분인 b에 대해서는 뒤쪽 루프를 돌며 나머지를 저장합니다. 이후 특정 위치에서 a에 대한 나머지가 0이고, 바로 다음 인덱스에서 b에 대한 나머지 역시 0이라면 그 지점이 바로 우리가 찾던 분할 지점이므로 해당 결과를 출력합니다.
이 방법의 시간 복잡도는 O(N)으로, 문자열의 길이에 선형적으로 비례하기 때문에 길이가 매우 긴 입력에서도 효율적으로 동작한다는 장점이 있습니다.
결론
이 튜토리얼에서는 숫자를 두 개의 나누어 떨어지는 부분으로 분할하는 문제를 해결해 보았습니다. 또한 이 문제를 위한 C++ 프로그램과 문제를 풀어내는 완전한 접근 방식을 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 작성할 수 있습니다. 이 튜토리얼이 여러분에게 도움이 되기를 바랍니다.