재귀함수 연습
링크:https://www.acmicpc.net/problem/2529
테스트 케이스
접근1
코드
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.2 정수 중복 체크도 10자리라 리스트에 저장하고 not in을 사용해도 될 것 같아서 사용했지만
자릿수가 늘어나면 반복 횟수도 그만큼 늘어나기 때문에 다른 방법으로 중복체크를 해야 할 것 같음
재귀 함수가 아직 익숙하지 않아서 로직 구현 시 시간이 너무 오래 걸림 좀 더 익숙해질 필요가 있음
이런 유용한 정보를 나눠주셔서 감사합니다.