문제 소개
이 문제에서는 큰 숫자를 나타내는 문자열과 중단점(breakpoint)의 개수를 의미하는 정수 k가 주어집니다. 목표는 숫자에 k개의 중단점을 넣은 후 만들 수 있는 최대 세그먼트 값을 찾는 프로그램을 작성하는 것입니다.
쉽게 말해, 문자열로 주어진 숫자를 k개의 중단점으로 여러 구간으로 나누었을 때 생성될 수 있는 가장 큰 숫자를 구하는 것입니다.
예시를 통해 문제를 자세히 이해해 보겠습니다.
입력 − string = "45972", k = 3
출력 − 97
설명 −
가능한 모든 분할 결과: 45 9 7 2 4 59 7 2 4 5 97 2 4 5 9 72 모든 경우 중 97이 가장 큰 숫자입니다.
접근 방법: 슬라이딩 윈도우 기법
이 문제는 슬라이딩 윈도우(Sliding Window) 기법을 활용하면 효율적으로 해결할 수 있습니다.
k개의 중단점을 넣으면 숫자는 k+1개의 세그먼트로 나뉘며, 최대 세그먼트의 길이는 (문자열 길이 − k)가 됩니다. 따라서 이 길이를 가진 모든 연속된 부분 문자열을 검사하여 그중 최댓값을 찾으면 됩니다.
매번 숫자를 처음부터 다시 계산하는 대신, 이전 윈도우 값에서 맨 앞 자릿수를 빼고 새로운 자릿수를 뒤에 붙이는 방식으로 다음 윈도우 값을 상수 시간에 구할 수 있으므로 전체 시간 복잡도는 O(n)입니다.
C++ 구현 예제
숫자에 K개의 중단점을 넣은 후 최대 세그먼트 값을 찾는 프로그램 −
#include <bits/stdc++.h>
using namespace std;
int findMaxSegmentWithKbreaks(string &s, int k) {
int window = s.length() - k;
int MaxNumber = 0;
for (int i=0; i<window; i++)
MaxNumber = MaxNumber * 10 + (s[i] - '0');
int slWindow = pow(10, window-1);
int value = MaxNumber;
for (int i = 1; i <= (s.length() - window); i++) {
value = value - (s[i-1]- '0')*slWindow;
value = value*10 + (s[i+window-1]- '0');
MaxNumber = max(MaxNumber, value);
}
return MaxNumber;
}
int main() {
string s = "45972";
int k = 3;
cout<<"Maximum segment value after putting "<<k<<" break points in a number = "<<findMaxSegmentWithKbreaks(s, k);
return 0;
}코드 동작 원리
- window: 최대 세그먼트의 길이로, 문자열 길이에서 k를 뺀 값입니다.
- 첫 번째 반복문은 첫 번째 윈도우에 해당하는 숫자 값을 초기화합니다.
- slWindow는 윈도우에서 가장 높은 자릿값(10^(window−1))으로, 맨 앞 자릿수를 제거할 때 사용됩니다.
- 두 번째 반복문에서는 윈도우를 한 칸씩 오른쪽으로 이동시키며, 앞 자릿수를 빼고 새로운 자릿수를 더한 뒤 최댓값을 갱신합니다.
출력 결과
Maximum segment value after putting 3 breakpoints in a number = 97
마무리
이처럼 슬라이딩 윈도우 기법을 활용하면 숫자에 k개의 중단점을 넣었을 때 얻을 수 있는 최대 세그먼트 값을 선형 시간 O(n) 안에 효율적으로 구할 수 있습니다. 이 접근 방식은 문자열 처리 및 최적화 문제에서 널리 활용되는 핵심 패턴이므로 잘 익혀두면 다양한 알고리즘 문제 해결에 큰 도움이 됩니다.