[CodeJam][2017] Tidy Numbers - Qualification Round B

문제 : https://code.google.com/codejam/contest/dashboard?c=3264486#s=p1

---

let) 문자열 N = "441"

문자열 N으로 (N[index], index)를 하나의 요소로 하는 배열을 만든다음 N[index] 기준으로 오름차순 정렬한다.

이 배열을 앞에서부터 탐색하면서(let, 탐색 중인 인덱스 = i) index가 탐색 중인 인덱스 i와 다를때까지 정답 문자열에 N[i]를 차례대로 넣는다.

index와 i 가 다른 경우는 N[i] 보다 작은 숫자가 이후에 나온다는걸 의미한다.

위의 예시에서는 i가 0일 때, index는 2이다. N[i] = 4보다 작은 N[index] = 1이 이후에 나오기 때문이다.

index와 i가 다를 때를 찾았으면 오름차순이 안될 때까지 정답배열에 N[i]를 차례대로 넣는다.

예시에서는 441 을 모두 넣었을 때 오름차순이 어긋난다.

이제 정답 배열에 있는 가장 뒤에 있는 문자를 9로 만들고 이전 숫자에 -1 해준다. 

만약 오름차순이 깨진다면 오름차순이 깨지지 않을 때까지 앞에 수를 -1 해준다.

그리고 -1 해준 뒤에 값을 9로 만든다. (339 < 399 이기 때문)

4121로 예를 들어보면 위에서 말한데까지 정답을 구하면 39가된다.

이후 남은 숫자들은 모두 최대값이 9로 채워준다.

만약 정답 배열에 가장 앞에 숫자가 0이라면 삭제해준다.

입력 값 N의 최대값이 10^18이기 때문에 문자열로 계산해준다.

오름차순이 안될 때까지 정답 배열을 만들고, 뒤에서부터 앞으로 탐색하면서 오름차순이 깨지지 않을때까지 정답을 갱신하므로 시간복잡도는 O(|N|^2).

헷갈렸던 TC.

441 -> 399 

11122233441 -> 11122233399

---

소스코드 : https://gist.github.com/fpdjsns/0b134e7011b94c548b394a77b70e7fa2