16943번 - 숫자 재배치

1. 숫자 재배치

• 난이도
  • 실버 1
• 시간 제한
  • 2초
• 메모리 제한
  • 512MB
• 출처
  • 16943번: 숫자 재배치 (acmicpc.net)

A. 📜 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

B. 💡 내 답안

a. 😊 1차 시도 (성공)

from itertools import permutations

def check_len(A_len, B_len):
    if A_len > B_len:
        return False
    return True

def solution(A, B):
    possible = check_len(len(A), len(B))
    answer = -1

    if possible:
        permu = list(permutations(A, len(A)))

        for p in permu:
            # print(permu)
            if p[0] != '0':
                value = int(''.join(p))
                B = int(B)

                if value < B:
                    answer = max(value, answer)
                else:
                    continue

    return answer

if __name__ == "__main__":
    A, B = list(input().split())

    print(solution(A, B))

b. 🙄 회고

내 풀이

• 순열을 이용해서 풀었다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

nPn 순열 자체가 굉장히 많은 연산(n!)이 필요하다.

그런데 문제의 수의 범위가 최대 $10^9$이라서 최대 10! (3,628,800)개의 원소를 확인해야한다. 그리고 파이썬은 1초에 최대 2000만번 연산을 진행하므로 단순 순열로 문제를 해결할 수 있다.

그래도 연산은 최소한으로 하는 것이 좋아서 불가능한 경우들을 먼저 걸러냈다.

1. A의 길이가 B보다 긴 경우
   • 이 경우는 어떤 방식으로 A를 조합해도 B보다 작은 수가 나올 수 없다.
2. 순열의 원소가 0부터 시작하는 경우 (첫번째 자리가 0인 경우)
   • 문제에서 0부터 시작하면 안 된다는 조건이 주어졌다.
3. 구한 값이 B보다 큰 경우
   • 이 문제의 목표가 B보다 작은 가장 큰 수이기 때문에, B보다 큰 경우는 제외했다.

참고문헌

baekjoon. 16943번: 숫자 재배치 (acmicpc.net). Baekjoon. (accessed Dec 8, 2021)