[SWAE] 1244

• 요점 정리
  - 완전 탐색
  - for문 + 재귀로 완전 탐색을 구현
  - 최대 횟수만큼 교환한경우, 숫자를 최대값과 비교해서 저장
  - 더이상 교환할 수 없는 상황인데, 교환 횟수 소진을 다 못한경우 짝수, 홀수 나눠서 끝자리수 교환
  - 현재 인덱스, 남은 교환횟수 를 파라미터로 수행하는 함수 작성
  - 탐색 후 상태를 원상복구
  - str을 list로 변환해 swap등의 작업 이후 최종 숫자 비교 단계에서 숫자로 변환
  - 최댓값, 최대 교환횟수 등을 전역변수로 사용

def dfs(idx, cnt):
    global max_num
    global swap_cnt

    if cnt == swap_cnt:
        if max_num < int(''.join(num_str)):
            max_num = int(''.join(num_str))
        return

    if cnt < swap_cnt and idx == (len(num_str) - 1):
        rem_cnt = swap_cnt - cnt
        if rem_cnt % 2 == 0:
            if max_num < int(''.join(num_str)):
                max_num = int(''.join(num_str))
        else:
            tmp = num_str[-1]
            num_str[-1] = num_str[-2]
            num_str[-2] = tmp

            if max_num < int(''.join(num_str)):
                max_num = int(''.join(num_str))

            tmp = num_str[-1]
            num_str[-1] = num_str[-2]
            num_str[-2] = tmp
        return

    flag = False
    for i in range(idx, len(num_str)):
        for j in range(i+1, len(num_str)):
            if num_str[i] <= num_str[j]:
                flag = True

                tmp = num_str[i]
                num_str[i] = num_str[j]
                num_str[j] = tmp

                dfs(i, cnt+1)

                tmp = num_str[i]
                num_str[i] = num_str[j]
                num_str[j] = tmp

    if not flag:
        dfs(len(num_str) - 1, cnt)

    return

n = int(input())
for test_case in range(n):
    num_str, swap_cnt = input().split()
    swap_cnt = int(swap_cnt)
    max_num = 0
    num_str = list(num_str)
    dfs(0, 0)
    print('#%d %d'%(test_case+1, max_num))