문자열이 주어졌을 때, 재배열하여 원본보다 사전 순으로 느린 문자열 중 사전 순으로 가장 빠른 문자열을 찾는 간단한 문제를 하나 생각해봅시다.
가능한 모든 재배열 방법을 확인하는 건 $N!$에 비례하는 시간이 걸리기 때문에 다른 방법을 찾아보아야 합니다.
이 문제를 해결하기 이 글에서 소개하고자 하는 풀이 방법을 이용해 소개하고자 합니다. 확정되지 않은 가장 앞자리에 a를 넣어본 뒤에 가능한지 확인한 후, 가능하다면 확정 지어주고 불가능하다면 다음 문자인 b로 넘어가고, 이를 확정 짓기까지 계속 반복하는 것입니다.
예를 들어 문제의 입력으로 babca 라는 문자열이 주어졌다고 합시다. 가장 앞의 자리에 a를 넣어 정답이 될 문자열을 a _ _ _ _ 이라고 생각하고 가능한지 확인해보는 겁니다. 지금 상태에서 남은 문자를 어떻게든 배치해도 babca보다 사전 순으로 느린 문자열을 만들 수는 없어 보입니다. 그럼 넘어가서 a 대신 b를 넣는다고 생각해봅시다. b _ _ _ _ _ 은 문제의 정답이 될 수 있을지는 바로 눈에 보일지도 모르지만, 일단은 가능한지 불가능한지 모르는 상태로 b를 넣은 지금의 상태가 babca보다 느린 문자열을 만들 수 있을지 확인하는 방법을 찾아야 합니다.
현재 상태에서 만들 수 있는 가장 사전 순으로 느린 문자열이 원본 문자열보다 사전순으로 느리다면 그 문자를 넣은 상태로도 원본 문자열보다 사전순으로 느린 문자열을 만들 수는 있다는 뜻이므로 확정 지어 다음 확정되지 않은 자리로 넘어가면 됩니다.
사전 순으로 가장 느린 문자열은 남은 문자들을 내림차순으로 정렬해서 만든 문자열의 뒤에 붙으면 구할 수 있고, 이렇게 만든 문자열이 원본 문자열보다 느리다면 다음 문자로 넘어가지 않고 현재 자리를 확정지은 이후 다음 문자로 넘어가면 됩니다. 사전순은 앞에 나오는 자리일수록 더 중요한 값이기 때문에 확정시킬 수 있다면 다음 문자로 넘어가지 않고 바로 확정해도 문제에서 요구하는 문자열을 찾을 수 있습니다. 이렇게 앞에서부터 하나씩 문자열의 모든 자리를 확정 지으면 되고, 이를 코드로 보면 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string s;
char left_alphabet[256];
int main(){
cin >> s;
int N = s.size();
for(int i=0;i<N;i++) left_alphabet[s[i]]++; // 사용되지 않은 문자들을 저장합니다.
string ans;
for(int i=0;i<N;i++) ans.push_back(0);
for(int i=0;i<N;i++) { // 가장 앞의 자리부터 하나씩 확정지어 나갑니다.
for(int c='a';c<='z';c++) if(left_alphabet[c] > 0) { // a부터 z까지 하나씩 반복
ans[i] = c, left_alphabet[c]--;
int u = i+1;
for(int x='z';x>='a';x--) { // 남은 문자들을 내림차순으로 정렬해 만든 문자열의 가장 뒤에 붙입니다.
for(int j=1;j<=left_alphabet[x];j++) ans[u++] = x;
}
if(ans > s) break; // 구한 문자열이 원본 문자열보다 느리다면 확정 짓고 다음 자리로 넘어갑니다.
left_alphabet[c]++;
}
}
cout << ans;
}
위 코드는 판정을 $O(eN)$번 해야하고 한번 판정하는데 $O(N)$이 걸리므로 $O(eN^2)$의 시간복잡도를 가지지만 사실 이 방법 말고 C++의 std::next_permutation을 이용해 $O(N)$에 문제를 해결할 수 있습니다. 글의 주제를 설명하기 위해 조금 돌아가지만 앞의 방법대로 앞의 문자를 하나씩 확정짓는 방식을 이용해 푸는 방법을 소개했습니다.
이 방법은 앞의 문자를 확정 지어 사전 순 최소 혹은 최대를 구하는 방법뿐만 아니라 수의 위의 자릿수를 확정 지어 최솟값 혹은 최댓값을 구하는 방식으로 응용할 수 있습니다. 다음 문제를 봅시다.
BOJ 1040
가장 위의 자릿수부터 $1$부터 $9$까지 순서대로 넣어본 다음 가능한지 확인해봅시다. 그 상태에서 가능한 가장 큰 수를 찾아 $N$보다 큰 수가 될 수 있는지 확인한다면, 더 큰 숫자로 넘어가지 않고 그 숫자로 확정지어도 $N$보다 큰 수를 만들 수 있다는 것이기 때문에 그 자릿수에서 확정지을 수 있는 가장 작은 숫자가 됩니다.
이제 확인하는 방법을 생각해봅시다. 앞에서 선택한 서로 다른 숫자의 개수를 $X$라고 하면, $X$는 $K$를 초과해선 안 됩니다. 만약 $X$가 $K$보다 작다면 $K-X$만큼의 사용하지 않았던 숫자를 선택해서 추가해줘야 하고, 당연하게도 사용하지 않은 숫자 중 큰 순으로 선택해야 합니다. 그럼 선택한 $K-X$개의 수를 내림차순으로 수의 가장 아래 자리에 붙여주고, 남은 자리에 사용한 숫자 중 최댓값으로 중간을 채워주면 최댓값을 구할 수 있습니다. 말로 표현하면 조금 어렵지만, 다음 예제를 보면 금방 이해할 수 있을 거라 생각합니다.
$K = 4$이고 현재 수는 8XXXXX로 확정을 지은 상태입니다. 남은 가장 높은 자릿수에 $1$을 넣는다고 하면 81XXXX가 되고, 아직 $2$개의 숫자를 더 사용해 주어야 하므로 남은 숫자 중 가장 큰 $9$와 $7$을 선택해 뒤에 붙여줍니다. 그러면 수는 81XX97이 되고, 사용한 숫자 중 가장 큰 숫자인 $9$를 남은 자리에 모두 채워준다면 819997이 되어 $1$을 만의 자리에 넣었을 때 가능한 최댓값을 구할 수 있습니다.
이를 통해 위의 자릿수부터 가능한 가장 작은 숫자로 하나씩 확정지을 수 있으므로 최소를 구해야 하는 문제의 정답을 찾을 수 있습니다.
BOJ 1071
문제에서 주어진 배열을 내림차순으로 정렬한다면 주어진 조건을 만족하는 배열을 만들 수 있지만, 우리는 사전 순으로 가장 앞서는 배열을 구해야 하므로 이건 항상 답이 될 수 없습니다. 위와 마찬가지로 앞에서부터 배열에서 사용하지 않은 가장 작은 값부터 하나씩 넣어본 다음 가능한지 판별하면 될 텐데, 이 문제에서는 판별을 단순히 앞의 두 문제처럼 최댓값 혹은 최솟값으로 만들어서 해결할 수 없습니다.
이 문제는 앞에서 설명한 두 문제와는 조금 다른 방식을 사용해서 풀어야 합니다.
앞에 확정지은 배열 $A[0:i]$는 당연히 조건을 만족한다고 보고, 현재 값을 넣은 위치가 $i$라고 할 때 남은 수들을 내림차순으로 정렬한 다음 뒤에 붙이면 $A[i]+1 \neq max$인 경우를 제외하고 조건을 만족하는 배열을 만들 수 있습니다. 하지만 $A[i]+1 = max$인 경우 이 방법으로 조건을 만족하는 배열을 만들 수 없으므로 아이디어가 하나 필요한데, 사용하지 않은 수 중 $A[i]$와 $A[i]+1$이 아닌 값을 가져와 확정된 배열과 뒤에 붙일 배열 사이에 이 값을 넣으면 조건을 만족하게 됩니다.
이를 조금 더 생각해보면 남은 수들의 최댓값이 $A[i]+1$이고, 최솟값이 $A[i]$ 또는 $A[i]+1$인 경우만 아니면 조건을 만족하는 배열을 만들 수 있고, 그 경우면 어떻게 배치하더라도 $A[i]$ 다음에 $A[i]+1$가 나오기 때문에 조건을 만족하는 배열을 만들 수 없음을 알 수 있습니다. 그러므로 남은 수의 최댓값과 최솟값을 알 수 있다면 가능한지 간단히 판별할 수 있습니다.
$N$개의 위치마다 $N$개의 수를 하나씩 넣어보는 방법을 사용하고, 판별은 수의 범위가 $1\,000$이하라는 점을 이용해 남은 수의 개수를 별도의 배열로 관리하면 $O(1)$에 가능하므로 이 풀이의 시간복잡도는 $O(N^2)$입니다.
BOJ 1426
문제에서 요구하는 정답이 사전 순 최소이므로 A가 쓰여 있는 카드부터 Z가 쓰인 카드까지 차례로 시도해야 하는데, 우리는 같은 문자가 쓰였지만 다른 정수가 쓰여있는 카드가 있으면 어떤 순서대로 해야 할지 처리해야 합니다. 더 큰 정수가 적혀있는 카드의 선택지가 더 작은 정수가 적혀있는 카드의 선택지를 포함하므로 더 적은 범위에서 사용할 수 있는 작은 정수가 적힌 카드를 먼저 사용해야 이득임을 알 수 있습니다. 그러므로 카드를 문자의 오름차순으로, 문자가 같다면 정수의 오름차순으로 정렬하고 앞에서부터 하나씩 넣어봅시다.
이제 앞선 문제들처럼 가능한지 판정해야 합니다. 문자는 생각하지 않고 단순히 통에 쓰인 정수와 카드의 정수만 고려해주면 됩니다. 정수가 작은 카드를 넣을 수 있는 통은 더 큰 정수의 카드를 넣을 수 있지만 정수가 더 큰 카드를 넣을 수 있는 통을 더 작은 카드가 넣을 수 없는 통이 존재할 수 있습니다. 그러므로 카드의 정수가 작은 순서대로 가능한 아무 통에나 넣는 방법을 사용한다면 항상 판별할 수 있습니다. 그러므로 $O(N \log N)$에 판별이 가능하고, 전체 시간복잡도 $O(N^3 \logN)$에 문제를 해결할 수 있습니다.
문제를 풀다가 조건을 만족하는 최소 혹은 최댓값을 구하는 문제를 마주친다면 한 번쯤은 생각해볼 만한 방법이라 생각하고, 각 자리에 들어갈 수 있는 후보의 개수가 숫자나 문자처럼 작으면서 판정법이 $O(N)$보다 작은 방법이 있다면 $N$이 크더라도 사용할 수 있으므로 소개한 앞의 문제들과 달리 $N$이 크다고 무작정 이 방법을 배제하지는 않았으면 합니다.
끝으로, 이 글의 주제로 풀 수 있는 연습 문제 몇 개를 올리고 글을 마치도록 하겠습니다.