파이썬) 부등호 - BOJ

https://www.acmicpc.net/problem/2529

2529번: 부등호

 

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으로 시도했지만 시간초과... 이후 백트레킹으로 해도 시간초과... 결국 정답을 참조했따