[Silver I] 숫자 재배치 - 16943

문제 링크

성능 요약

메모리: 100324 KB, 시간: 360 ms

분류

백트래킹, 브루트포스 알고리즘, 조합론, 수학

제출 일자

2024년 11월 2일 22:22:49

문제 설명

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다.

가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

풀이

 

나의 잘못된 접근 (Greedy 이용)

import sys
 
 
A , B = map(str , sys.stdin.readline().split())
 
a = [int(i) for i in A]
b = [int(i) for i in B]
 
 
r = []
 
 
next = False
 
for i in b:
    tmp = []
    if(next):
        i = i * 10
 
    for w in a:
        if(i-w >=0):
            if(w not in r):
                tmp.append(w)
    if(tmp !=[]):
        r.append(max(tmp))
        if(i-max(tmp) != 0):
            next = True 
 
 
if(len(r)< len(A)):
    print(-1)
 
 
 
else:
    for _ in r:
        print(_, end = "")

 

 

순열을 이용한 풀이

 

import sys
from itertools import permutations
 
# 파일에서 입력 받기
sys.stdin = open("input.txt", "r")
 
# A와 B를 문자열로 입력받기
A, B = sys.stdin.readline().split()
B = int(B)  # B를 정수로 변환하여 비교
 
# 가능한 모든 순열을 생성
perms = permutations(A)
max_result = -1
 
for perm in perms:
    # 순열을 숫자로 변환
    num = int("".join(perm))
    
    # 조건: B보다 작고, 숫자가 0으로 시작하지 않아야 함
    if num < B and str(num)[0] != '0':
        max_result = max(max_result, num)
 
# 결과 출력: 가능한 값이 없으면 -1 출력
print(max_result)

 

 

백트랙킹을 이용한 풀이

import sys
 
A, B = sys.stdin.readline().split()
A_digits = sorted(A, reverse=True)  # A의 숫자를 내림차순으로 정렬
B = int(B)
visited = [False] * len(A_digits)  # 숫자 사용 여부를 체크하기 위한 리스트
max_result = -1
 
def find_max_number(current_num):
    global max_result
 
    # 숫자를 모두 선택했다면, 현재 숫자가 B보다 작은지 확인
    if len(current_num) == len(A):
        num = int(current_num)
        if num < B:
            max_result = max(max_result, num)
        return
    
    # 자리별로 숫자를 선택하여 가능한 최대값 찾기
    for i in range(len(A_digits)):
        if not visited[i]: 
            # 첫 자리에서 0으로 시작하면 안 됨
            if current_num == "" and A_digits[i] == '0':
                continue
            visited[i] = True
            find_max_number(current_num + A_digits[i])  
            visited[i] = False
 
 
find_max_number("")
 
 
print(max_result)
저작자표시 비영리

티스토리툴바