이제 슬슬 파이썬에 익숙해지는 것 같당!
근데 이러다가 c++이랑 파이썬 둘다 못하는 0개언어 사람이 되버리면 어떡하지 ㅎㅅㅎ,,
이 문제는 원석오빠가 백트레킹 문제를 풀어보라고 준 문제이담!
근데 씨쁠에서 파이썬으로 바꾼 뒤로 백트레킹을 처음 풀어보는게 레전드,,
감두 안와서 블로그들 보면서 해봤는데 설명이 길게 나와있는 블로그가 없었답 ㅜ 쉬운문제여서 그런거같당
그래서 코드를 계속 보면서 이해해보려고 했는데 처음엔 그것도 잘 안됐당..
근데 한번 이해가 되고 난 뒤로는 실마리가 풀리는 느낌이었담!
생각보다 쉬운거였어서 왜 사람들이 설명을 길게 안 적어놨는지 알 것 같았다 왜냐면 쓸말이 정말 없기 때문..
그래도 아직 혼자 코드 짜라고 하면 못짜겠어서.. 반복하고 외우는것만이 살길이다 ㅠㅠ!
num = int(input())
op = input().split()
mx, mn = "", "" # 최대, 최소숫자
check = [False]*10 # 백트래킹 체크할 배열
def verify(a, b, c): # 해당 자리에 숫자가 들어갈 수 있는지 검증
if c == '>':
return a>b
else:
return a<b
def fun(depth, s): # 재귀함수 호출 DFS
global mx, mn
if depth == num+1: # 끝까지 도달했을때
if len(mn) == 0: # 0부터 9로 가다보니 처음성공한게
mn = s # 제일 최소
else:
mx = s # 최대는 계속 갱신
return
for i in range(10): # 0 - 9 까지
if not check[i]:
if depth == 0 or verify(s[len(s)-1], str(i), op[depth-1]):
# depth가 0이면 오류나서
check[i] = True # 체크하고
fun(depth+1, s+str(i)) # 재귀부르고
check[i] = False # 재귀 끝나면 체크해제
fun(0,"") # 무에서 시작
print(mx)
print(mn)
🐢👩💻⛄🤍💜