백준 2529 부등호

1~9 까지의 숫자를 나열하여 주어진 부등호를 만족하는 최대 최소 값을 찾는 문제.

최대 최소이므로 뽑을 수 있는 숫자 범위는 1~9이며 뽑아야하는 갯수는 부등호 + 1개이다.

백트래킹으로 풀기

def dfs(pick):
    global ans
    if len(pick) == n+1:
        ans.append(''.join(map(str, pick)))
        return
    for i in range(10):
        if not visit[i]:
            visit[i] = True
            pick.append(number[i])
            dfs(pick)
            pick.pop()
            visit[i] = False

dfs는 부등호+1개 만큼의 원소를 뽑아 ans에 저장하는 모든 경우의 수이다. 여기서 부등호를 판단해서 처리하면 된다.

순열로 풀기

n = int(input())
number = [0,1,2,3,4,5,6,7,8,9]
s = list(map(str, input().split(" ")))
minv, maxv = 0, 0
lis = []

for c in permutations(number, len(s) + 1):
    flag = True

    for idx in range(len(c) - 1):
        if c[idx] > c[idx+1]:
            if s[idx] == "<":
                flag = False
                break
        if c[idx] < c[idx+1]:
            if s[idx] == ">":
                flag = False
                break
    if flag:
        lis.append(''.join(map(str, c)))

print(lis[-1])
print(lis[0])

두번째 for문에서 len(c)-1만큼 하는 이유는 부등호의 갯수만큼만 돌리면 되기 때문이다.

주의할것 = list의 int문 join

str 자료형만 join이 되기 때문에 오류가 발생함 -> join 안에 map으로 list를 str 형변환 시켜줘야함.