처음에는 너무 쉬운 그리디 알고리즘 문제라고 생각하였다. 가장 첫째자리부터 현재 자리에서 그 다음 자리의 숫자들 중 현재 자리의 숫자보다 큰 수가 존재하면 가장 큰 수와 위치를 바꿔주면 된다고 생각하였다.
코드는 다음과 같다.
import sys
input = sys.stdin.readline
def change():
same = False
for i in range(L-1):
x = numlist[i]
y = -1
yi = -1
for j in range(i+1,L):
if numlist[j] >= y:
yi = j
y = numlist[j]
if y > x:
numlist[i] = y
numlist[yi] = x
return
elif y == x:
same == True
if same:
return
numlist[i] = numlist[j]
numlist[j] = x
N,K = map(int,input().split())
numlist = [*map(int,[*str(N)])]
L = len(numlist)
if L <= 2 and sum(numlist[1:]) == 0:
print(-1)
else:
for i in range(K):
change()
print("".join(map(str,numlist)))
그러나 이 코드는 틀렸습니다 가 떴다.
이 코드는 앞자리 수보다 큰 같은 수가 여러개 존재하는 경우에 대해 처리하지 못하는 문제점이 있었던 것이다.
예를들어서 3199 2 라는 코드가 있다면, 3199 >> 9193 >> 9913 과 3199 >> 9139 >> 9931 로 처리할 때, 두 수의 크기가 달라지게 된다. 따라서 이런 중복숫자에 대해서 모두 비교를 해주어야 하는 것이다.
따라서 그리디 알고리즘만 사용하는 것이 아니라 그리디 + 브루트포스를 혼합하는 것이 필요했다.
코드는 다음과 같다.
import sys
input = sys.stdin.readline
def DFS(num,cnt):
global result
if cnt == K:
result = max(result,num)
return
numlist = [*map(int,[*str(num)])]
for i in range(L-1):
x = numlist[i]
y = -1
for j in range(i+1,L):
if numlist[j] > y:
changelist = [j]
y = numlist[j]
elif numlist[j] == y:
changelist.append(j)
if y > x:
for c in changelist:
newnumlist = numlist[:]
newnumlist[i] = y
newnumlist[c] = x
DFS(int("".join(map(str,newnumlist))),cnt+1)
return
if same:
result = max(result,num)
return
newnumlist = numlist[:]
newnumlist[-1] = numlist[-2]
newnumlist[-2] = numlist[-1]
DFS(int("".join(map(str,newnumlist))),cnt+1)
N,K = map(int,input().split())
L = len(str(N))
same = False
for i in range(10):
if str(N).count(str(i)) > 1:
same = True
break
if L <= 2 and sum([*map(int,[*str(N)])][1:]) == 0:
print(-1)
else:
result = 0
DFS(N,0)
print(result)
알고리즘을 처음부터 요약하면,
0. 모든 숫자들 중 같은 숫자가 존재하는지 확인한다 (4번에서 필요)
1. 일단 숫자의 길이가 1이거나 2이면서 두번째 숫자가 0인 경우에는 -1을 출력한다.
2. 앞서 말했던 것처럼 가장 첫째자리부터 현재 자리에서 다음 자리의 숫자들 중 가장 큰 숫자와 위치를 바꾼다.
3. 2번에서 가장 큰 수가 여러개 존재할 경우 브루트 포스로 모든 경우를 탐사한다.
4. 만약 모든 숫자가 크기순으로 정렬된 경우, 같은 숫자가 존재하는 경우 그 값을 출력한다.
5. 같은 숫자가 존재하지 않으면 가장 마지막 자릿수와 두번째 마지막 자릿수의 위치를 교환한다.
6. 결과를 출력한다.
오늘의 교훈) 예외되는 케이스들에 대해서 잘 고려하자