[Codejam][2021][Round 1A] 1. Append Sort

문제 : https://codingcompetitions.withgoogle.com/codejam/round/000000000043585d/00000000007549e5

---

이전 숫자를 prev, 현재 탐색 중인 숫자를 now라 하자. 

now > prev가 되도록 숫자를 now뒤에 추가해야 한다.

 

만약 prev가 now보다 작다면 추가 digit 없이 조건을 만족하므로 다음 숫자를 탐색한다. prev의 자리수가 now 자리수보다 작다면 반드시 prev가 now보다 작으므로 이 경우에 속한다. ex) prev = 10, now = 8

 

prev와 now의 자리수가 동일하다면 now 뒤에 숫자 0을 추가한다. ex) prev = 10, now = 10 => 100

 

이 외의 경우는 prev의 자리수가 now 자리수보다 큰 경우이다. now 문자열의 길이만큼의 prev 문자열의 prefix를 구해서 prefixPrev라 하자. ex) prev = 123, now = 10 => prefixPrev = 12

i) prefixPrev < now : now 뒤에 prev 자리수와 동일하게끔 0을 뒤에 추가한다. ex) prev = 1234, now = 13 => now = 1300

ii) prefixPrev > now : now 뒤에 prev 자리수보다 1 커지게끔 0을 뒤에 추가한다. ex) prev = 1234, now = 11 => now = 11000

iii) prefixPrev == now : prev에 1을 더한 값의 now 자리수만큼의 prefix가 now와 동일하다면 now를 해당 숫자로 갱신한다. ex) prev = 9998, now = 99, prev+1 = 9999 (prefix 동일) => now = 9999

     prev에 1을 더한 값의 now 자리수만큼의 prefix가 now와 동일하지 않다면 prev+1이 자리수가 하나가 추가된다는 뜻이다. now의 기존 수는 변경할 수 없고 뒤에 숫자만 추가할 수 있으므로 prev길이 + 1 길이가 되도록 now 숫자 뒤에 0을 추가한다. ex) prev = 9999, now = 99, prev+1 = 10000 (prefix 동일하지 않음) => now = 99000

 

시간복잡도는 O(TNM), T = tc 수. N = 배열크기. M=배열요소 자리수

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/2021/round1A/1.%20Append%20Sort.cpp​​