[백준] 2529 - 부등호 (Python)

문제 출처 : 

www.acmicpc.net/problem/2529

2529번: 부등호

문제 풀이 :

• 문제를 분할해서 생각해보자. 
  
  • 새로 추가되는 숫자에 대한 부등호 관계가 만족하는가?
  • 새롭게 추가되는 숫자를 중복없이 어떻게 만들 것인가?
  • 최소와 최대를 어떻게 구할 것인가? (따로 구분해주기)
• 위의 서브 문제들을 풀어가보자
  • 새로운 숫자가 추가 될때 마다 앞에 숫자랑 비교해주는 함수를 만들자(check 함수)
  • 백트래킹을 이용해보자. 숫자는 중복없이 0~9까지이므로 for문 돌려서 사용하면된다. 
    • 이때 어차피 check에서 안되는 건 따로 만들 필요없으므로 가지치기를 진행해준다.
  • 만약 조건에 부합한 문자열이 처음 생긴거면 그게 제일 작은 거다. 그리고 제일 마지막에 구해진 녀석이 제일 큰 녀석이다 (애초에 시작할때 0부터 커지는 순서로 for문을 돌렸으니까.)

n = int(input())
ine_sing = list(map(str,input().split()))

visited = [0]*10
max_ans =""
min_ans =""

def check(i,j,k):
    if k=='<':
        return i<j
    else:
        return i>j

def solve(idx,s):
    global max_ans,min_ans

    if(idx==n+1):
        if(len(min_ans)==0):
            min_ans = s
        else:
            max_ans = s
        return
    for i in range(10):
        if(visited[i]==0):
            if(idx==0 or check(s[-1],str(i),ine_sing[idx-1])):
                visited[i]=True
                solve(idx+1,s+str(i))
                visited[i]=False


solve(0,"")
print(max_ans)
print(min_ans)