[백준] 2529 - 부등호

1. 문제

2529번: 부등호

2. 개요

오늘도 백트래킹.

0~9 까지의 수를 하나씩 사용해 주어진 부등호에 맞게 순서대로 넣으면 된다.

3. 코드 및 추가 내용

3-1. 시간초과 코드

import sys

k = int(sys.stdin.readline())

nums = [i for i in range(10)]
ops = list(sys.stdin.readline().split())
ans = []

def bt(idx, l):
    global ans
    if idx == k+1:
        ans.append(l)

    else:
        for i in range(10):
            if eval(str(l[-1]) + ops[idx-1] + str(i)) == True and i not in l:
                bt(idx + 1, l + [i])

for i in range(10):
    bt(1, [i])

print(''.join(list(map(str, ans[-1]))))
print(''.join(list(map(str, ans[0]))))

조건이 되는 부등식은 그냥 문자열을 식으로 변환하는 eval을 써서 대충 떼웠다.

첫 수를 백트래킹 함수의 인자로 넣고 이후에 조건을 달아 함수를 돌려봤는데 시간초과였다.

3-2. ok 코드

그래서 일단 이것저것 건드려봤는데

import sys

k = int(sys.stdin.readline())

nums = [i for i in range(10)]
ops = list(sys.stdin.readline().split())
ans = []

def bt(idx, l):
    global ans
    if idx == k+1:
        ans.append(l)

    else:
        for i in range(10):
            if i in l:
                continue
            if eval(str(l[-1]) + ops[idx-1] + str(i)) == True:
                bt(idx + 1, l + [i])

for i in range(10):
    bt(1, [i])

print(''.join(list(map(str, ans[-1]))))
print(''.join(list(map(str, ans[0]))))

그냥 중복처리할때 if문 하나를 따로 빼주니까 시간초과 안뜨더라.