16943번 - 숫자 재배치

  • 0
  • 0
0
0

1. 숫자 재배치

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)

0 minutes ago
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.