BOJ 2529 부등호 PYTHON

재귀함수 연습
링크:https://www.acmicpc.net/problem/2529

테스트 케이스

접근1

1. 최솟값을 구할 때 0~9, 최댓값을 구할 때 9~0의 수를 부등호를 기준으로 +-1씩 해가며 재귀 호출로
   탐색을 시도
2. 중복체크를 위해 정수를 하나씩 리스트에 저장하여 중복체크
3. 최소, 최대 정수를 하나씩만 구하면 되니 적절하게 재귀 호출을 끝낼 조건을 만들어본다

코드

import sys
input = sys.stdin.readline

n = int(input())
ilist = input().split()
ans = []
tmp = []
def f1(idx):
    if len(tmp) == n+1:
        ans.append(tmp[:])
        return
    for x in range(0,10): 
        if len(ans) <= 0:
            if (ilist[idx] == '<' and tmp[idx] < x) or (ilist[idx] == '>' and tmp[idx] > x):
                if x not in tmp:
                    tmp.append(x)
                    f1(idx+1)   
                    tmp.pop()          
def f2(idx):
    if len(tmp) == n+1:
        ans.append(tmp[:])
        return
    for x in range(9,-1,-1): 
        if len(ans) <= 0:
            if (ilist[idx] == '<' and tmp[idx] < x) or (ilist[idx] == '>' and tmp[idx] > x):
                if x not in tmp:
                    tmp.append(x)
                    f2(idx+1)   
                    tmp.pop()  
for x in range(9,-1,-1):
    if len(ans) <= 0:
        tmp.append(x)
        f2(0)
        tmp.pop()
print(''.join(map(str,ans[0])))
ans.pop()
for x in range(10):
    if len(ans) <= 0:
        tmp.append(x)
        f1(0)
        tmp.pop()
print(''.join(map(str,ans[0])))

f1 = 부등호를 만족하고 이전 숫자와 중복되지 않는 수를 0부터 +1 하며 탐색
f2 = 부등호를 만족하고 이전 숫자와 중복되지 않는 수를 9부터 -1 하며 탐색

f1, f2 각각 탐색이 완료된 시점은 부등호의 개수+1을 하여 리스트의 길이를 비교하여
체크하고 조건을 만족시킨 정수 리스트를 저장할 다른 리스트에 저장하여 적절하게 종료하려 함

결과

느낀점

1. 문제를 해결하긴 하였으나 별로 효율적이지 못한 거 같음
   1.1 재귀 호출이 끝까지 탐색을 하진 않으나 좀 더 효율적으로 종료시킬 수 있을 거 같음
   1.2 정수 중복 체크도 10자리라 리스트에 저장하고 not in을 사용해도 될 것 같아서 사용했지만
   자릿수가 늘어나면 반복 횟수도 그만큼 늘어나기 때문에 다른 방법으로 중복체크를 해야 할 것 같음

2. 재귀 함수가 아직 익숙하지 않아서 로직 구현 시 시간이 너무 오래 걸림 좀 더 익숙해질 필요가 있음