[SWEA] 정곤이의 단조 증가하는 수 / Python / D3

🚩문제 주소

📄풀이

먼저 dfs를 활용해서 A[i] * A[j]한 결과를 문자열로 바꿔서 set에 저장합니다.

N이 1이라면 set에 입력받은 하나의 수만 저장합니다.
그 외에는 dfs를 실행합니다.

저장된 set을 list로 바꿔주고 반복문을 돌려 각 원소에 대해 앞 인덱스의 수가 뒤 인덱스의 수보다 크다면 flag를 False로 바꿉니다.

flag가 True라면 정답 배열에 int로 바꿔서 넣어주는데, 바꾼 수가 한 자리 수라면 넣지 않습니다.

정답 배열에 아무것도 없다면 -1를 출력하고, 있다면 최댓값을 출력합니다.

👨‍💻코드

def dfs(cnt, num):
  if cnt == 1:
    arr.add(str(num))
    return
  for i in range(N):
    for j in range(i+1, N):
      visited[i],visited[j] = 1,1
      dfs(cnt+1, A[i]*A[j])
      visited[i],visited[j] = 0,0

T = int(input())
for tc in range(1, T+1):
  N = int(input())
  A = list(map(int, input().split()))
  visited = [0]*N
  arr = set()
  answer = []

  if N == 1:
    arr.add(str(A[0]))
  else:
    dfs(0, 0)
  arr = list(arr)

  for a in arr:
    flag = True
    
    for i in range(len(a)-1):
      if a[i] > a[i+1]:
        flag = False
    
    if flag:
      temp = int(a)
      if temp > 9:
        answer.append(temp)
  
  if len(answer) == 0:
    print(f'#{tc} {-1}')
  else:
    print(f'#{tc} {max(answer)}')