이 문제의 의도는 쉬워보이는 척 (실제로도 쉽지만) 하면서 마음이 급한 참가자들을 낚기위함 이었습니다.
-_-; 스코어 보드를 보니 제 목표는 달성한 듯 합니다. (D를 빨리 풀어줘서 더 많은 참가자들이 떡밥을 물게 해준 2등팀에게 감사드립니다)
이 문제의 풀이는 의외로 간단합니다. 우선 몇 가지 observation이 필요합니다.
주어진 n과 k, 그리고 정답 m을 생각해 봅시다. (m은 anagram of n)
m의 가장 큰 자리 부터 k와 비교를 할 때 3가지 경우가 가능합니다
1) k보다 작다
2) k와 같다
3) k보다 크다
3)
의 경우, m의 나머지 숫자들 (즉 현재 자리수보다 작은 자리에 있는 숫자들)은 비내림차순 정렬이 되어있어야 합니다. 아니라면,
정렬 안된 숫자들을 정렬해서 m보다 더 작은 m'을 만들 수 있고, m' 이 m보다 lucky lucky number에
가깝습니다.
비슷하게 1)의 경우, 현재 자리수보다 작은 자리에 있는 숫자들은 비오름차순 정렬이 되어야 합니다. 아니라면 그 수들을 정렬해서 m보다 더 큰 m'을 만들 수 있고 m'이 m보다 lucky lucky number에 가깝습니다.
2)의 경우, tie-break가 일어나는 (1이나 3의 경우에 해당하는) 자리수 까지 가는 경우가 있고 혹은 정답 m (그리고 n)이 아예 lucky lucky number인 경우가 있습니다.
어쨌거나 정답에 대한 observation이 힌트를 줍니다 (backtracking):
첫 자리 수로 어떤 수 x를 시도했을 때:
1) x 2) x=k, then 다음 자리 수 try
3) x>k, then sort the rest (정순)
이 backtracking이 찾아내는 모든 답을 lucky lucky number랑 비교하면서 가장 근접한 (그 중에 가장 큰) 수를 찾으면 답이 됩니다.
물론 더 좋은(빠른?) 방법이 있습니다. (대회 때에는 200자리 정도로 제한한 이유가, 백트래킹으로도 나올지 모른다는 희망을 불어넣기 위해서 였습니다... 나오는지 안 나오는지 저는 안 해봐서 모릅니다^^; 일루님이라면 가능할 듯)
만약 주어진 수 n이 몇 개의 k를 포함했을 경우, 그 'k'들은 정답에서 어디에 위치할까요? 가장 큰 자리수들에
자리합니다 (즉 가장 왼쪽). 간단하게 증명할 수 있습니다. 첫 자리수가 k로 시작하는 anagram C, 첫 자리수가 k보다 큰 a로 시작하는
anagram A, k보다 작은 b로 시작하는 anagram B 세 가지를 생각해 봅시다.
lucky lucky number를 X라 해봅시다.
Let us write A = a_1a_2 ... a_l, C = c_1c_2 ... c_l, and X = x_1x_2 ... x_l = kk ... k (total l k's).
A가 정답인 경우, |A - X| = A - X > |C - X| for any C. A가 정답이라 가정하고 모순을 이끌어 내보겠습니다.
A의 경우 첫 자리가 a>k 이고, 나머지 수들은 비내림 차순 정렬이 되어있습니다. 이제 C는 첫 자리수를 k로 고정하고, 두번째 자리수를 a로 놓습니다. 물론 나머지 자리수들은 비내림 차순 정렬이 되어야 겠죠. 그러면 |A-X| > |C-X|가 되므로 A가 정답이라는 가정에 어긋납니다. 즉, 첫 자리수가 k가 아닌 경우, 첫 자리수를 k로 만들면서 더 좋은 해를 찾을 수 있다는 뜻이 됩니다. 마찬가지로 B의 경우도 B로부터 첫 자리수를 k로 고정하면서 더 좋은 해를 찾아낼 수 있습니다.
따라서 우리는 다음과 같은 결론에 도달하게 됩니다:
given n, if dig[i] is the number of occurrences of digit i in n, the following algorithm gives the desired answer:
1) if dig[k] > 0 then place all k's at the beginning of the number
2) for all a > k and b < k, fix the next digit after 1) (it can be the first digit, or dig[k]+1-th digit) as a (and b). sort appropriately the rest digits, and compare such answers.
2번은 즉, k=7인 경우, 첫 자리수 (7을 모두 앞에 배치한 후에 남은 수들 중)를 1, 2, 3, 4, 5, 6, 8, 9, 0 모두 시도해보면서 그 중 가장 근접한 수 (그 중 가장 큰 수)를 찾으면 그 수가 답이 된다는 말입니다.
이제 여기서 한 번 더 optimize를 할 수 있는데 (needless), 실제로는 최대 2개의 수만 만들어보면 된다는 점 입니다.
k = 7인 경우, 첫 자리수를 8과 6만 시도해보고 비교해보면 됩니다. 만약 n에 8이나 6이 없다면, 9와 5를 비교해보면 됩니다. 즉, k로부터 +- 1인 수를 첫 자리수로 고정시켜보고, 그런 수가 전혀 없으면 +-2를, +-3을, ..., 하면 되겠습니다.
마지막으로 제가 투척한 떡밥은, 우선 예제에서도 잘 드러나듯이 모든 정답이 lucky lucky number보다 같거나 큽니다. 즉, 왠지 k=7이고 6과 8이 준재한다면, 8로 시작하여 만든 수가 답이 될 것 같은 느낌을 줍니다. 불행히도 작은 수가 더 근접한 경우도 있습니다. n = 99559와 k=7을 생각해보세요:
lucky lucky number보다 작은 수는 59995 이고 큰 수는 95599 입니다. 59995가 95599보다 77777에 더 근접합니다.
또, 문제에서 leading zero에 대한 부분 언급이 있었는데 n이 자연수이기 때문에 이 부분은 전혀 고려할 필요가 없습니다. 답은 항상 첫 자리수가 0보다 크게 나올 것이기 때문이죠.
=) 짧게 정리해서 말하면, greedy한 접근으로 모든 k를 최대한 앞에 전부 배치하고, k에 가장 가까운 수 (1가지 일 수도 있고 2가지 일 수도 있음)를 첫 수로 고정한 후 나머지를 적절히 정렬하여 (비오름/비내림) 결과로 얻은 수 (1개 혹은 2개)의 차이값을 비교하여 출력하면 됩니다.
혹시 이해가 안 가는 부분이나 잘못 된 점 등, 지적할 부분은 코멘트 남겨주시기 바랍니다. =D