알고리즘
파이썬) 부등호 - BOJ
1일1공부실천하자
2023. 11. 10. 16:40
https://www.acmicpc.net/problem/2529
2529번: 부등호
여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력
www.acmicpc.net
k = int(input())
arr = [i for i in range(10)]
string = list(map(str, input().split()))
result = []
def dfs(k, arr, string, current):
if len(current) == k + 1:
num_str = ''.join(map(str, current))
is_True = True
for i in range(len(string)):
if string[i] == '<' and num_str[i] >= num_str[i+1]:
is_True = False
break
elif string[i] == '>' and num_str[i] <= num_str[i+1]:
is_True = False
break
if is_True:
result.append(num_str)
return
for num in arr:
if num not in current:
dfs(k, arr, string, current + [num])
dfs(k, arr, string, [])
print(result[-1])
print(result[0])이 문제는 시간초과가 많이 발생했따.
처음 작성한 코드는 아래와 같다
from itertools import permutations
k = int(input())
arr = [i for i in range(10)]
string = list(map(str, input().split()))
result = []
for per in permutations(arr, k+1):
s = f'{per[0]}'
for i in range(len(string)):
s += string[i]
s += str(per[i+1])
if eval(s):
num = int(''.join(map(str, per)))
result.append(num)
result.sort()
print(result[-1])
print(result[0])permutation으로 시도했지만 시간초과... 이후 백트레킹으로 해도 시간초과... 결국 정답을 참조했따