[백준 1039번] 교환 (Python3)

처음에는 너무 쉬운 그리디 알고리즘 문제라고 생각하였다. 가장 첫째자리부터 현재 자리에서 그 다음 자리의 숫자들 중 현재 자리의 숫자보다 큰 수가 존재하면 가장 큰 수와 위치를 바꿔주면 된다고 생각하였다.

 

코드는 다음과 같다.

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. 결과를 출력한다.

 

 

오늘의 교훈) 예외되는 케이스들에 대해서 잘 고려하자