# 16943번 - 숫자 재배치

- Author: @mildsalmon
- Published: 2021-12-08
- Updated: 2021-12-08
- Source: http://blex.me/@mildsalmon/16943%EB%B2%88-%EC%88%AB%EC%9E%90-%EC%9E%AC%EB%B0%B0%EC%B9%98
- Tags: 파이썬, 알고리즘, 수학, 코딩테스트, 문제, 백준

---

# 1. 숫자 재배치

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

### A. 📜 문제

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

### B. 💡 내 답안

##### a. 😊 1차 시도 (성공)

```python

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](https://www.acmicpc.net/user/baekjoon). [16943번: 숫자 재배치 (acmicpc.net)](https://www.acmicpc.net/problem/16943). Baekjoon. (accessed Dec 8, 2021)