문제

코드

import sys 
input = sys.stdin.readline

k=int(input())
arr = input().split()
visited = [0]*10
MAX,MIN = "",""

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

def bt(cnt,string):
    global MAX,MIN
    if cnt > k :
        if len(MIN)==0: #제일 처음 들어오는거 
            MIN = string
        else : 
            MAX = string #이후 MAX에 넣음 
        return #함수반환 
    for i in range(10):
        if visited[i]==0: #아직 방문 전 
            if cnt==0 or check(string[-1],str(i),arr[cnt-1]): #0이면 무조건 담꺼 붙여야함 ㅇㅇ check(string제일마지막꺼,추가될거,부호)
                visited[i]=1
                bt(cnt+1,string+str(i))
                visited[i]=0


bt(0,"")
print(MAX)
print(MIN)

해설

내가 만든 코드는 메모리 차지를 어마어마하게 엄청 비효율적인 방법이라서 다른 사람들의 코드를 둘러봤다..
역시..나 백트렉킹이였다..
백트랙킹 이제는 익혀야하고 익숙해져야한다.. 이만큼 나왔는데 안익숙해지면 사람도 아니지 젠쟝,,,
쨌든 백트랙킹의 주요 포인트는 재귀라는점을 잊지말자.

보일지는 모르겠지만 이해를 바탕으로 설명하겠다.
우선 , MAX,MIN 을 문자열로 만들어준다는게 인상깊었고
for문에서 0~9까지 돌리므로 어차피 최솟값부터 최댓값까지 쭉 순서대로 진행된다는 점이다.

그 점을 이용해서 백트랙킹 함수안에서는 제일 처음 cnt>k의 조건을 만족하는 문자열에 MIN이 아직 한번도 안들어왔다면 그 값을 MIN에 넣어서 최솟값을 구한다.

그리고 그 이후에 들어오는 값들은 전부 MIN보다 큰 값일테니
MAX에다가 넣어 MAX를 매번 초기화 시켜준다.
그 후 반환해주어 백트랙킹을 종료하는 방식으로 진행되는데
밑에 for문이 약간 인상깊었다.

왜냐면.. cnt =0 또는 check함수를 활용하는것인데
cnt=0이라는것은 이것이 제일 처음도는 함수라는것이다.
그렇다면 문자열을 비어있을태고 그 문자열에는 들어오는 i를 넣고 cnt+1해주어서 재귀를 가서 cnt=1이 되는 순간에는 check함수를 돌면서 참여부를 판단하는것이다.

그런데 check함수로 값을 줄때 string[-1]이 부분도 인상이 깊었는데, 그 이유는 stirng에서 마지막 값과 들어올 수 있는 i의 값을 비교하기위해서 string[-1]을 사용한다는 점이다.

또한 arr에는 부등호를 받았는데, range(10)까지 도는 포문에서 i로 arr를 탐색하면 인덱스 범위를 넘어가므로 cnt-1로 하는 방법 또한 신박했다..

아직 배울것이 많은 백트렉킹이다..!