[백준] 16943번 숫자 재배치

💡문제접근

• from itertools import permutations를 이용해서 푸는 방법과 백트래킹을 이용한 방법 두 가지로 접근할 수 있을 것 같아 두 가지 방법으로 풀어보았다.

💡코드(메모리 : 100460KB, 시간 : 672ms)

from itertools import permutations
import sys
input = sys.stdin.readline

A, B = map(str, input().strip().split())
B = int(B)
C = -1

li = list(permutations(A))
res = []
for i in li:
    res.append("".join(map(str, i)))

for i in res:
    if i[0] == "0":
        continue
    i = int(i)
    if i < B:
        C = max(C, i)
print(C)

📌백트래킹 풀이 방법(메모리 : 31256KB, 시간 : 952ms)

import sys
input = sys.stdin.readline

A, B = map(str, input().split())
A = list(A)
B = list(B)
length = len(A)
checked = [False] * length
C = -1

# 이 때, current_num은 문자처럼 취급한다는 점을 주의할 것
def recursive(idx, current_num):
    global C
    if idx == length:
        if int(current_num) <= int(''.join(map(str, B))):
            C = max(C, int(current_num))
        return
    for i in range(length):
        if idx == 0 and A[i] == "0":
            continue
        if not checked[i]:
            checked[i] = True
            recursive(idx + 1, current_num + A[i])
            checked[i] = False

recursive(0, '')
print(C)

• 주어진 테스트케이스 중에서 1000 5의 출력이 계속 1이 나와 어떤 부분이 문제였는지 계속 보았다. if idx == 0 and A[i] == "0": 이 부분에서 처음엔 A[i] == 0:으로 작성했는데 이 부분에서 오류가 발생해서 정답이 계속 1로 출력된 것이다. 문자열 0001을 정수형으로 변환하면 1이 되는데 이 값은 5보다 작거나 같은 가장 큰 값이 되기 때문에 1이 출력되는 것으로 보인다. A[i] == "0":처럼 문자 0으로 표시해주어야 문제가 발생하지 않게 된다.

• 백트래킹의 중요 요소

  • 재귀
  • 체크 배열

💡소요시간 : 10m + 40m